Euler Function

오일러 함수

페르마 소정리는 자연수 세계의 성질을 더 깊이 이해하는데 획기적인 발전의 디딤돌 역할을 하였다. 오일러는 페르마의 연구나 가설들을 체계적으로 연구하고 발전시켰다. 페르마 소정리를 일반화한 정리에서 나온 개념이 '어떤 자연수 n보다 작으면서 서로소인 관계에 있는 수'의 개념이었다. 오일러가 도입한 이 개념은 페르마 정리가 그랬던 것처럼 수학의 세계를 풍요롭게 하는데 중요한 디딤돌이 되었다.

정의

주어진 두 자연수에 대하여 그 두 수가 서로 소관계에 있는가 하는 문제가 지금까지 나온 여러 정리에서 중요한 조건이 된다는 것은 이미 보아왔다. 여기서 호기심을 발동시켜 다음의 관계가 있다고 해보자. 어떤 주어진 n 에 대하여

(x, n) = 1

가 되는 x에 관심을 기울여보는 것이다. 예를들어 n이 7 이라면,

(x, 7) =1

이 될 수 있는 x는 1,2,3,4,5,6,8,9,10, ... 이 된다. x가 n보다 큰 경우는 의미없어 보이므로 우리의 관심을 n보다 작거나 같은 수들로 제한하여 보자. 그렇다면

(x, 3) =1 인 x 는 1,2

(x, 6) =1 인 x 는 1,5

(x, 9) =1 인 x 는 1,2 , 4, 5, 8

(x, 24) = 1 인 x 는 1, 5, 7, 11, 13, 17, 19, 23이 된다.

이와 관련하여 그 개수를 나타내는 함수를 오일러 함수라고 부른다.

오일러 함수 : 어떤 자연수 n에 대하여 그 수보다 작으면서 그 수와 서로소인 수의 개수를 나타내는 함수 ( $\mathbb {N} \rightarrow \mathbb {N}$)를 오일러 함수라 한다.

이 오일러 함수는 보통 $\varphi (n)$로 쓴다.

성질

소수의 곱으로 표현한 자연수 n에 $\varphi (n)$ 일반식

어떤 자연수 n에 대하여 일반적인 함수규칙 $\phi (n)$을 추적해보자. n은 산술의 기본정리에서

$n=p_{1}^{\alpha _{1}}\cdot p_{2}^{\alpha _{2}}\cdot p_{3}^{\alpha _{3}}\cdots p_{k}^{\alpha _{k}}$

로 나타낼 수 있다. 따라서 가능한 n의 경우를 나누어 생각하면서 일반화된 함수 규칙 $\varphi (n)$을 찾자.

• n이 소수라면

$\varphi (n)=n-1$

이라는 것은 분명하다. 소수는 그보다 작은 수들과는 언제나 서로소 이기 때문이다.

• n이 소수의 k-제곱이라면, 다시 말해 $p^{k}$라면

$\varphi (p^{k})=p^{k}-p^{k-1}$

이다. 예를들어 $3^{3}$이라면 그보다 작은 자연수는 26개이고 그 안에 서로소가 아닌 것들은 3, 6, 9, ..., 24까지 있고 이것들을 모두 3으로 나누면 1,2,3, ..., 8까지 $\varphi (3^{3-1})$라는 점을 생각하면서 일반화하면 이해할 수 있다.

• n이 두 서로다른 소수 p와 q의 곱이라면 $\varphi (p\cdot q)=\varphi (p)\cdot \varphi (p)$

인 성질을 갖는다. pq보다 작은 모든 서로소인 수들은 pq 자신보다 작은 모든 자연수에서 p로 나누어지는 수나 q로 나누어지는 수를 뺀 수 일 것이다. 이는 p로 나누어 떨어지는 수이고 q로 나누어 떨어지는 수일 것이다.

• 따라서 위의 사실들을 응용하여, 수학적 귀납에 따라, 일반적으로 n에 대하여

$\varphi (n)=\varphi \left(p_{1}^{\alpha _{1}}\cdot p_{2}^{\alpha _{2}}\cdot p_{3}^{\alpha _{3}}\cdots p_{k}^{\alpha _{k}}\right)=\left(p_{1}^{\alpha _{1}}-p_{1}^{\alpha _{1}-1}\right)\cdot \left(p_{2}^{\alpha _{2}}-p_{2}^{\alpha _{2}-1}\right)\cdots \left(p_{r}^{\alpha _{r}}-p_{r}^{\alpha _{r}-1}\right)=n\cdot \left(1-{\frac {1}{p_{1}}}\right)\cdot \left(1-{\frac {1}{p_{21}}}\right)\cdots \left(1-{\frac {1}{p_{r}}}\right)$

이 된다.

이로써 우리는 어떤 자연수 n이 주어졌다면 그 수보다 작거나 같고 서로소인 자연수들의 개수를 얻을 수 있는 알고리듬을 짤 수 있다.

• 모든 n에 대하여 소수들의 곱으로 나누어 표현한다.
• 참여한 서로 다른 소수들과 n을 곱셈, 뺄셈, 나눗셈을 연산한다.

그렇지만 문제는 소수들의 곱으로 나타내는 연산이 가장 계산이 복잡한 알고리듬이니 사실, 알고리듬적으로는 단순하지 않다.

$\phi (n)$의 기초 성질들

• 2보다 큰 모든 n에 대해 $\varphi (n)$은 짝수다.

오일러 함수의 응용

자연수라는 구체적인 수를 대상으로하는 연구에서 등장한 오일러 함수는 19세기 말 이후 수학이 추상화되어 보다 광범위하게 발전해가는 동안 중요한 역할을 하고 있다. 여기서는 구체적인 예를 들어 본다. 자세한 설명은 공부한 다음... 나중에....

• 골드바흐 추측이 사실이라면, 어떤 자연수 n 에 대해서도 아래의 관계를 만족하는 소수 p,q가 존재한다 :

$\varphi (p)+\varphi (q)=2n$

Related

• 산술의 기본정리
• 유클리드 알고리듬

Math : Math글쓰기 | Math번역 | MathBoard | Math&Culture | MathMoim
OnLineMathCenter | MathCamp | SoftMathJournal | MathBook | CyberAcademia | Academia