[정수론](8)[오일러 정리]

 

오일러 ϕ 함수

ϕ(m) = {a| 1<=a<=m, gcd(a, m) = 1}의 원소의 개수

• 예)
  ϕ(1) = 1
  ϕ(2) = 1
  ϕ(3) = 2 ...

 

소수 p에 대해 a !≡ 0 (mod m) 을 만족하는 1~ϕ(m)개의 b의 배수 bna (mod m)는
1, 2, ..., bn을 재배열한 것과 같다.

• 증명
  gcd(b1, m) = 1이면 gcd(ab1, m) = 1이다.
  이때 bja, bka가 법 m에 대해 합동이라 가정한다. (1<= j, k <= m-1)
  bja ≡ bka (mod m)이므로 m|(j-k)a이다. p∤a 이므로 소수의 가약성에 의해 p|(bj-bk)이다.
  그러나 (1<= j, k <= m-1) 이므로 |j-k|<m-1
  따라서 bj-bk = 0 -> bj = bk이다
  m에 대해 합동인 수 bja = bka이므로 합동이면 전부 같은 숫자다.
  0이 아닌 ϕ(m)개의 합동이 아닌 수 목록은 1~ϕ(m)이므로 따라서 재배열이다.
  
  -> 즉, b1a, b2a, ..., bϕ(m)a (mod p)와 b1, b2, ..., bϕ(m) (mod m)는 순서만 다르지 같은 배열이다.

 

오일러 공식

gcd(a, m)=1이면 a^(ϕ(m)) ≡ 1 (mod m)이다.

• 증명
  위에서 한 증명에 의해 b1a, b2a, ..., bϕ(m)a (mod p)와 b1, b2, ..., bϕ(m) (mod p)는 같은 배열이다.
  따라서 b1a * b2a *...* bϕ(m)a ≡ b1*b2*...*bϕ(m) (mod m)
  모든 b에 대해 gcd(b, m)=1이므로 양 변을 b1b2...bϕ(m)로 나눌 수 있다.
  따라서 a^(ϕ(m)) ≡ 1 (mod m)