편집토론기록

오일러 피 함수


Euler's phi function, Euler's totient function

Euler's blood function이 아니다!

정수론에서[편집 | 원본 편집]

정수론에서 [math]\displaystyle{ \phi\left(n\right) }[/math]은 [math]\displaystyle{ n }[/math]보다 작거나 같은 양의 정수 중에서 [math]\displaystyle{ n }[/math]과 서로소인 수의 개수를 나타내는 함수다. 예를 들면, 6보다 작거나 같은 수 중에 6과 서로소인 수는 1, 5의 두 개 뿐이므로 [math]\displaystyle{ \phi\left(6\right)=2 }[/math]가 된다.

성질[편집 | 원본 편집]

  1. 임의의 양의 정수 [math]\displaystyle{ n }[/math]의 기약잉여계의 원소의 수는 [math]\displaystyle{ \phi\left(n\right) }[/math]이다.
  2. [math]\displaystyle{ \gcd\left(a,n\right)=1 }[/math]인 정수 [math]\displaystyle{ a }[/math]에 대해 [math]\displaystyle{ a^{\phi\left(n\right)}\equiv1\pmod n }[/math]이 성립한다.
  3. [math]\displaystyle{ p }[/math]가 소수면, [math]\displaystyle{ \phi\left(p\right)=p-1 }[/math]이다. 역도 성립한다.
  4. 소수 [math]\displaystyle{ p }[/math]에 대해 [math]\displaystyle{ \phi\left(p^a\right)=p^a-p^{a-1} }[/math]이다.
  5. 오일러 피 함수는 곱셈적 함수이다. 즉, 서로소인 양의 정수 [math]\displaystyle{ m,\,n }[/math]에 대해 [math]\displaystyle{ \phi\left(mn\right)=\phi\left(m\right)\phi\left(n\right) }[/math]가 성립한다.
  6. [math]\displaystyle{ n=p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k} }[/math]라 하자 (단, [math]\displaystyle{ p_i }[/math]는 서로 다른 소수, [math]\displaystyle{ a_i }[/math]는 자연수). 그럼 [math]\displaystyle{ \phi\left(n\right)=n\left(1-\frac{1}{p_1}\right)\left(1-\frac{1}{p_2}\right)\cdots\left(1-\frac{1}{p_k}\right) }[/math]이다.
  7. [math]\displaystyle{ n\gt 2 }[/math]이면 [math]\displaystyle{ \phi\left(n\right) }[/math]는 짝수다.
  8. [math]\displaystyle{ m\mid n }[/math]이면 [math]\displaystyle{ \phi\left(m\right)\mid\phi\left(n\right) }[/math]이다.
  9. [math]\displaystyle{ \phi\left(n^k\right)=n^{k-1}\phi\left(n\right) }[/math]
  10. [math]\displaystyle{ \sum_{d\mid n}\phi\left(d\right)=n }[/math]

증명[편집 | 원본 편집]

  1. 기약잉여계의 정의에 의해 자명하다.
  2. 오일러의 정리 참조.
  3. 쉬우므로 생략. 증명은 독자에게 연습문제로 남긴다.
  4. [math]\displaystyle{ p^a }[/math]와 서로소가 아닌 수는 [math]\displaystyle{ p }[/math]를 반드시 약수로 가져야 한다. 이는 곧 [math]\displaystyle{ p }[/math]의 배수를 의미하고, [math]\displaystyle{ p^a }[/math]보다 작거나 같은 [math]\displaystyle{ p }[/math]의 배수는 [math]\displaystyle{ p^a\div p=p^{a-1} }[/math]이다. [math]\displaystyle{ \therefore\phi\left(p^a\right)=p^a-p^{a-1} }[/math]
  5. 1부터 [math]\displaystyle{ mn }[/math]까지의 정수를 다음과 같이 나타내자.
1 m+1 2m+1 … (n-1)m+1
2 m+2 2m+2 … (n-1)m+2
[math]\displaystyle{ \vdots }[/math] [math]\displaystyle{ \vdots }[/math] [math]\displaystyle{ \vdots }[/math] [math]\displaystyle{ \vdots }[/math]
r m+r 2m+r … (n-1)m+r
[math]\displaystyle{ \vdots }[/math] [math]\displaystyle{ \vdots }[/math] [math]\displaystyle{ \vdots }[/math] [math]\displaystyle{ \vdots }[/math]
m 2m 3m … mn

만약 [math]\displaystyle{ \gcd\left(r,m\right)=d\neq1 }[/math]이면, [math]\displaystyle{ d\mid r,\,d\mid m }[/math]이므로 [math]\displaystyle{ d\mid km+r }[/math]이다. 즉, [math]\displaystyle{ \gcd\left(km+r,mn\right)\geq d }[/math]. 따라서 [math]\displaystyle{ r }[/math]번째 줄은 [math]\displaystyle{ mn }[/math]과 서로소인 정수를 포함하고 있지 않다. 만약 [math]\displaystyle{ \gcd\left(r,m\right)=1 }[/math]이면, [math]\displaystyle{ r }[/math]번째 줄에는 [math]\displaystyle{ r,\,m+r,\,2m+r,\,\cdots,\,\left(n-1\right)m+r }[/math]를 포함하고 있고, 이 수들은 [math]\displaystyle{ m }[/math]과 서로소이다. 만약 서로소가 아니라면, [math]\displaystyle{ d\neq1 }[/math]인 [math]\displaystyle{ d }[/math]에 대해 [math]\displaystyle{ d\mid m,\,d\mid km+r }[/math]이므로 [math]\displaystyle{ d\mid r }[/math]이 되어 [math]\displaystyle{ d\mid\gcd\left(m,r\right)=1 }[/math]이 되어 모순이다. 또한, 이 수들은 법 [math]\displaystyle{ n }[/math]에 대해 서로 다르다. 만약 [math]\displaystyle{ im+r\equiv jm+r\pmod n }[/math]이라면 [math]\displaystyle{ im\equiv jm\pmod n }[/math]이고, [math]\displaystyle{ \gcd\left(m,n\right)=1 }[/math]이므로 [math]\displaystyle{ i\equiv j\pmod n }[/math]이다. 그런데 [math]\displaystyle{ 0\leq i,\,j\leq n-1 }[/math]이므로 [math]\displaystyle{ i=j }[/math]여야만 한다. 정리하면, 저 수들은 법 [math]\displaystyle{ n }[/math]에 대해 기약잉여계를 구성한다. 1번 성질에 의해, 저 수들 중에 [math]\displaystyle{ n }[/math]과 서로소인 수의 개수는 [math]\displaystyle{ \phi\left(n\right) }[/math]이다. 한편, 저런 수들의 집합은 [math]\displaystyle{ \phi\left(m\right) }[/math]개 존재한다.
[math]\displaystyle{ \therefore\phi\left(mn\right)=\phi\left(m\right)\phi\left(n\right) }[/math].

6.
[math]\displaystyle{ \begin{align*}\phi\left(n\right)&=\phi\left(p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k}\right)\\&=\phi\left(p_1^{a_1}\right)\phi\left(p_2^{a_2}\right)\cdots\phi\left(p_k^{a_k}\right)\\&=\left(p_1^{a_1}-p_1^{a_1-1}\right)\left(p_2^{a_2}-p_2^{a_2-1}\right)\cdots\left(p_k^{a_k}-p_k^{a_k-1}\right)\\&=p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k}\left(1-\frac{1}{p_1}\right)\left(1-\frac{1}{p_2}\right)\cdots\left(1-\frac{1}{p_k}\right)\\&=n\left(1-\frac{1}{p_1}\right)\left(1-\frac{1}{p_2}\right)\cdots\left(1-\frac{1}{p_k}\right)\end{align*} }[/math]

7. 6번 성질에서 [math]\displaystyle{ \phi\left(n\right)=\prod_{i=1}^{k}\left(p_i^{a_i}-p_i^{a_i-1}\right)=\prod_{i=1}^{k}p_i^{a_i-1}\left(p_i-1\right) }[/math]임을 알 수 있다. 그런데 [math]\displaystyle{ n\gt 2 }[/math]이므로, [math]\displaystyle{ n }[/math]은 홀수인 소인수를 가지거나 소인수 2를 두 번 이상 가진다. 곧, 위 공식에서 [math]\displaystyle{ \phi\left(n\right) }[/math]가 짝수임을 유도할 수 있다.

8. [math]\displaystyle{ n=p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k} }[/math] ([math]\displaystyle{ a_i }[/math]는 자연수)라 하면, [math]\displaystyle{ m\mid n }[/math]이므로 [math]\displaystyle{ m=p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k} }[/math] ([math]\displaystyle{ a_i }[/math]는 음이 아닌 정수)가 된다. 6번 성질에서 [math]\displaystyle{ \phi\left(m\right)\mid\phi\left(n\right) }[/math]임이 바로 유도된다.

9. [math]\displaystyle{ n=p_1^{a_1}p_2^{a_2}\cdots p_m^{a_m} }[/math]라 하면, [math]\displaystyle{ n^k=p_1^{ka_1}p_2^{ka_2}\cdots p_m^{ka_m} }[/math]이다. 6번 성질을 적용하면 [math]\displaystyle{ \phi\left(n^k\right)=n^{k-1}\phi\left(n\right) }[/math]임이 바로 유도된다.

10. 1부터 [math]\displaystyle{ n }[/math]까지의 수를 다음과 같은 규칙에 의해 분류한다.

[math]\displaystyle{ \gcd\left(m,n\right)=d }[/math]이면 [math]\displaystyle{ m\in C_d }[/math]

그러면, [math]\displaystyle{ m\in C_d }[/math]이기 위한 필요충분 조건은 [math]\displaystyle{ \gcd\left(m/d,n/d\right)=1 }[/math]임을 알 수 있다. 곧, [math]\displaystyle{ \left|C_d\right|=\phi\left(n/d\right) }[/math]이다. 또한, [math]\displaystyle{ C_d }[/math]는 [math]\displaystyle{ n }[/math]의 partition임을 알 수 있다. 따라서, [math]\displaystyle{ n=\sum_{d\mid n}\phi\left(n/d\right) }[/math]. 그런데 모든 약수 [math]\displaystyle{ d }[/math]에 대해 값을 더하므로, [math]\displaystyle{ \sum_{d\mid n}\phi\left(n/d\right)=\sum_{d\mid n}\phi\left(d\right) }[/math].
[math]\displaystyle{ \therefore n=\sum_{d\mid n}\phi\left(d\right) }[/math]

추상대수학에서[편집 | 원본 편집]

추상대수학에서 오일러 피 함수는 조금 다르게 정의한다. 물론, 정수론적인 정의와 동치임을 증명할 것이다. 추상대수학 버전의 오일러 피 함수를 설명하기 전에 몇가지 용어를 정의한다.

  1. nth root of unity: [math]\displaystyle{ z^n=1 }[/math]인 복소수 [math]\displaystyle{ z }[/math]를 말한다.
  2. primitive nth root of unity: [math]\displaystyle{ \xi }[/math]가 nth root of unity이고, [math]\displaystyle{ n }[/math]이 [math]\displaystyle{ \xi^n=1 }[/math]를 만족하는 가장 작은 양의 정수라면, [math]\displaystyle{ \xi }[/math]를 primitive nth root of unity라 부른다.
  3. cyclotomic polynomial: [math]\displaystyle{ d }[/math]가 양의 정수일 때, dth cyclotomic polynomial을 [math]\displaystyle{ \Phi_d\left(x\right)=\prod\left(x-\xi\right) }[/math]로 정의한다. 여기서 [math]\displaystyle{ \xi }[/math]는 모든 primitive dth root of unity이다.

이제, 오일러 피 함수는 nth cyclotomic polynomial의 차수로 정의한다. 즉, [math]\displaystyle{ \phi\left(n\right)=\deg\left(\Phi_n\left(x\right)\right) }[/math].

성질과 증명[편집 | 원본 편집]

  1. 모든 nth root of unity [math]\displaystyle{ \xi }[/math]는 [math]\displaystyle{ e^{2\pi ik/n}=\cos\left(2\pi k/n\right)+i\sin\left(2\pi k/n\right) }[/math]과 동일하다 ([math]\displaystyle{ 0\leq k\leq n-1 }[/math]인 정수).
    • [math]\displaystyle{ \xi=\cos\left(2\pi/n\right)+i\sin\left(2\pi/n\right) }[/math]라 하면, 드 무아브르의 공식에 의해, [math]\displaystyle{ \xi^n=\left(\cos\left(2\pi/n\right)+i\sin\left(2\pi/n\right)\right)^n=\cos\left(2\pi\right)+i\sin\left(2\pi\right)=1 }[/math] 이다. 즉, [math]\displaystyle{ \xi }[/math]는 nth root of unity이다. 또한, [math]\displaystyle{ k }[/math]가 정수라면, [math]\displaystyle{ \left(\xi^k\right)^n=\left(\xi^n\right)^k=1^k=1 }[/math]이므로 [math]\displaystyle{ \xi^k }[/math] 역시 nth root of unity이다.
      역으로, [math]\displaystyle{ \xi }[/math]가 nth root of unity라 가정하자. [math]\displaystyle{ \left|\xi\right|=1 }[/math]이므로, 적당한 [math]\displaystyle{ \theta }[/math]에 대해 [math]\displaystyle{ \xi=\cos\theta+i\sin\theta }[/math]이다. 드 무아브르의 공식에 의해, [math]\displaystyle{ \xi^n=\cos n\theta+i\sin n\theta=1 }[/math]이다. 이 식은 [math]\displaystyle{ n\theta=2k\pi }[/math]는 일 때 성립한다. 또한, [math]\displaystyle{ \cos }[/math]의 주기가 [math]\displaystyle{ 2\pi }[/math]이므로 [math]\displaystyle{ 0\leq k\lt n }[/math]이라 해도 된다.
  2. [math]\displaystyle{ \xi }[/math]가 primitive dth root of unity라 가정하자. 만약 [math]\displaystyle{ \xi^n=1 }[/math]이면, [math]\displaystyle{ d\mid n }[/math]이다.
    • 나눗셈 정리에 의해, [math]\displaystyle{ n=qd+r }[/math], ([math]\displaystyle{ 0\leq r\lt d }[/math])이다. 그런데 [math]\displaystyle{ 1=\xi^n=\xi^{qd+r}=\xi^{qd}\xi^r=\xi^r }[/math]이다. 만약 [math]\displaystyle{ r\neq0 }[/math]이면, [math]\displaystyle{ d }[/math]가 [math]\displaystyle{ \xi^d=1 }[/math]를 만족하는 가장 작은 양의 정수라는 사실에 모순된다. 따라서 [math]\displaystyle{ r=0 }[/math]이고, [math]\displaystyle{ d\mid n }[/math]이다.
  3. 모든 자연수 [math]\displaystyle{ n }[/math]에 대해, [math]\displaystyle{ x^n-1=\prod_{d\mid n}\Phi_d\left(x\right) }[/math]이다.
    • 각 [math]\displaystyle{ n }[/math]의 인수 [math]\displaystyle{ d }[/math]에 대해, [math]\displaystyle{ \prod\left(x-\xi\right) }[/math]를 모아 곱하면 된다 ([math]\displaystyle{ \xi }[/math]는 primitive dth root of unity). 1번과 2번 성질이 필요하다는 점에 주목.
  4. 모든 자연수 [math]\displaystyle{ n }[/math]에 대해, [math]\displaystyle{ n=\sum_{d\mid n}\phi\left(d\right) }[/math]이다.
    • [math]\displaystyle{ \phi\left(n\right) }[/math]이 [math]\displaystyle{ \Phi_n\left(x\right) }[/math]의 차수라는 점과, 3번 성질과, 다항식의 차수는 인수의 차수들의 합이라는 사실을 이용하면 유도된다.
  5. [math]\displaystyle{ n }[/math]이 1이상인 정수일 때, [math]\displaystyle{ \phi\left(n\right) }[/math]는 [math]\displaystyle{ 1\leq k\leq n,\,\gcd\left(k,n\right)=1 }[/math]을 만족하는 정수 [math]\displaystyle{ k }[/math]의 개수이다.
    • 1번 성질에 의해 모든 nth root of unity는 [math]\displaystyle{ \xi=e^{2\pi ik/n} }[/math]이므로, [math]\displaystyle{ \xi }[/math]가 primitive란 것과 [math]\displaystyle{ \gcd\left(k,n\right)=1 }[/math]라는 명제가 동치임을 보이면 된다.
      만약 [math]\displaystyle{ k,\,n }[/math]이 서로소가 아니라면, 1보다 큰 적당한 정수 [math]\displaystyle{ d }[/math]에 대해 [math]\displaystyle{ n=dr,\,k=ds }[/math]가 성립한다. 또한, [math]\displaystyle{ r\lt n }[/math]라는 것을 알 수 있다. 따라서 [math]\displaystyle{ \frac{k}{n}=\frac{s}{r} }[/math]이고, [math]\displaystyle{ \left(e^{2\pi ik/n}\right)^r=\left(e^{2\pi is/r}\right)^r=1 }[/math]이므로 [math]\displaystyle{ e^{2\pi ik/n} }[/math]은 primitive nth root of unity가 아니다.
      역으로, [math]\displaystyle{ \gcd\left(k,n\right)=1 }[/math]이라 가정하자. 그럼 적당한 정수 [math]\displaystyle{ s,\,t }[/math]에 대해 [math]\displaystyle{ sk+tn=1 }[/math]이 성립한다. 한편, [math]\displaystyle{ \eta=e^{2\pi i/n} }[/math]라 정의하면, [math]\displaystyle{ \eta=e^{2\pi i/n}=e^{2\pi iks/n}e^{\pi int/n}=e^{2\pi iks/n}=\xi^s }[/math]이다. 만약 [math]\displaystyle{ 1\leq d\lt n }[/math]이고 [math]\displaystyle{ \xi^d=1 }[/math]인 [math]\displaystyle{ d }[/math]가 존재한다면 [math]\displaystyle{ \xi^{ds}=1=\eta^d }[/math]이다. 그런데 [math]\displaystyle{ \eta }[/math]는 primitive nth root of unity이므로 이는 모순이고, 조건을 만족하는 [math]\displaystyle{ d }[/math]는 존재하지 않음을 알 수 있다. 따라서 [math]\displaystyle{ \xi }[/math]는 primitive nth root of unity이다.

뭔 개소리야

관련 문서[편집 | 원본 편집]

각주