오일러 피 함수(Euler's Totient Function)
| 정의.1 |
φ(n) = |{ 1 ≤ i ≤ n | gcd(i, n) = 1 }| φ(n)는 n과 서로소의 관계가 있는 1과 n사이의 정수의 개수이다. |
예제) n = 1부터 15까지 각각의 φ(n)과 서로소 원소를 나열하자.
→ n = 1 일때, φ(1) = 1, { 1 }
→ n = 2 일때, φ(2) = 1, { 1 } (소수)
→ n = 3 일때, φ(3) = 2, { 1, 2 } (소수)
→ n = 4 일때, φ(4) = 2, { 1, 3 }
→ n = 5 일때, φ(5) = 4, { 1, 2, 3, 4 } (소수)
→ n = 6 일때, φ(6) = 2, { 1, 5 }
→ n = 7 일때, φ(7) = 6, { 1, 2, 3, 4, 5, 6 } (소수)
→ n = 8 일때, φ(8) = 4, { 1, 3, 5, 7 }
→ n = 9 일때, φ(9) = 6, { 1, 2, 4, 5, 7, 8 }
→ n = 10 일때, φ(10) = 4, { 1, 3, 7, 9 }
→ n = 11 일때, φ(11) = 10, { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 } (소수)
→ n = 12 일때, φ(12) = 4, { 1, 5, 7, 11 }
→ n = 13 일때, φ(13) = 12, { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 } (소수)
→ n = 14 일때, φ(14) = 6, { 1, 3, 5, 9, 11, 13 }
→ n = 15 일때, φ(15) = 8, { 1, 2, 4, 7, 8, 11, 13, 14 }
| 정리.1 |
| 두 정수 p, q가 서로소 일 때 φ(p * q) = φ(p) * φ(q) |
예제 1. φ(15) = φ(3*5) = φ(3) * φ(5) = 2 * 4 =8
| 정리.2 |
| p가 소수, e가 양의 정수일 때, φ(pe) = pe - p(e-1) = pe * (1 - 1/p) |
예제 2. φ(53) = 53 - 52 = 125 - 25 = 100
| 정리.3 |
| 임의의 정수 n이 소수들의 곱으로 표현된다면. φ(n) = n*(1 - 1/p1)* (1 - 1/p2)* ... *(1 - 1/pm) |
예제 3. n = 72 = 23 * 32
→ φ(72) = 72 * ( 1 - 1/2 ) * (1 - 1/3 ) = 72 * (1/2) * (2/3) = 24
| 정리.4 |
| 모든 양의 정수 n은 ∑d|n φ(d) = n , (여기서 d|n은 n을 나누는 약수) |
예제 4. n = 15일 때, ∑d|n φ(d) = n 계산
(1) 약수: d = { 1, 3, 5, 15 }는 약수를 가진다.
→ ∑d|n φ(d) = φ(1) + φ(3) + φ(5) + φ(15) = 15
(2) 정의.1에 따라서 n = 15일때, φ(15) = 8, 서로소 { 1, 2, 4, 7, 8, 11, 13, 14 }
(3) 약수 d 원소들에 대한 φ(d)를 계산
→ φ(15)는 최대공약수 gcd(15, 1) = 1, 원소가 8개 = { 1, 2, 4, 7, 8, 11, 13, 14 }
→ φ(5)는 최대공약수 gcd(15, 5) = 3, 원소가 4개 = { 3, 6, 9, 12 }
→ φ(3)는 최대공약수 gcd(15,3) = 5, 원소가 2개 = { 5, 10 }
→ φ(1)는 최대공약수 gcd(15,15) = 15, 원소가 1개 = { 0 }
∴ ∑d|n φ(d) = φ(1) + φ(3) + φ(5) + φ(15) = 1 + 2 + 4 + 8 = 15
| 정리.5 |
| 두 정수 a와 n이 서로소 일때, aφ(n) ≡ 1 (mod n) 만약 n = p 소수라고 하면, 모든 정수 a (1 ≤ a < p)는 소수 p와 서로소이며, φ(p) = p -1 이다. |
예제 5. a = 5, n = 13 (소수)
→ φ(13) = 12,
→ aφ(n) = 512 ≡ 1 (mod 13)