오일러 정리

오일러 피 함수

오일러 피 함수는 1~n 범위 중 n과 서로소인 숫자의 갯수를 구하는 함수이다.

• 1부터 6까지의 정수 중 6과 서로소인 수는 1, 5 두 개이므로 φ(6) = 2이다.
• 1부터 10까지의 정수는 모두 11과 서로소이고, 11은 자신과 서로소가 아니므로, φ(11) = 10이다.
• 1은 자기 자신과 서로소이므로, φ(1) = 1이다.

오일러 정리

오일러 정리는, 정수 a 및 양의 정수 n이 주어졌고 a와 n이 서로소일 때 아래 식이 성립한다는 내용이다.

a^φ(n) ≡ 1 (mod n)

페르마 소정리와 유사한 논리로 증명할 수 있다.

1. n과 서로소인 1부터 n까지의 정수를 r₁, r₂, …, r_φ(n)이라 하자. 이들의 개수가 바로 φ(n)개이다.

2. a가 n과 서로소일 때, ar₁, ar₂, …, ar_φ(n)을 n으로 나눈 나머지들도 모두 n과 서로소이며, 서로 다르다.

   • 만약 ar_i ≡ ar_j (mod n)이면, a의 역원을 양변에 곱하면 r_i ≡ r_j (mod n)이 되어 모순.
   • ar_i가 n과 서로소가 아니라면, gcd(ar_i, n) > 1이다. 그런데 gcd(a, n) = 1이고 gcd(r_i, n) = 1이므로 gcd(ar_i, n) = 1이어야 하므로 모순.

3. 따라서 {ar₁, ar₂, …, ar_φ(n)} mod n은 {r₁, r₂, …, r_φ(n)}의 순열이다.

4. 양변을 곱하면:

   (ar₁)(ar₂)...(ar_φ(n)) ≡ r₁r₂...r_φ(n) (mod n)
   a^φ(n) · (r₁r₂...r_φ(n)) ≡ r₁r₂...r_φ(n) (mod n)

5. r₁r₂…r_φ(n)은 n과 서로소이므로 곱셈 역원이 존재한다. 양변에 역원을 곱하면:

   a^φ(n) ≡ 1 (mod n)