📂정수론

오일러의 토션트 정리 증명

정리 ¹

$$ \gcd(a,m) = 1 \implies a^{ \phi (m) } \equiv 1 \pmod{m} $$

설명

보자마자 페르마의 소정리를 일반화한 정리임을 알 수 있고, 실제로 증명법도 사실상 거의 똑같다.

증명

토션트 함수의 정의에 의해, $1 \le b_{i} \le m$ 중 $\gcd( b_{i} , m) =1$ 을 만족하는 $b_{i}$ 는 정확히 $\phi (m)$ 개 존재한다. 이들의 집합을 $$ B:= \left\{ b_{1}, b_{2}, \cdots , b_{\phi (m)} \right\} $$ 라고 하자. 그러면 $\gcd(a,m) = 1$ 이므로 $$ aB = \left\{ ab_{1}, ab_{2}, \cdots , ab_{\phi (m)} \right\} $$ 와 정확히 같은 집합이 된다. 따라서 $$ b_{1} b_{2} \cdots b_{\phi (m)} \equiv ab_{1} ab_{2} \cdots ab_{\phi (m)} \pmod{m} $$ 우변의 $a$ 를 묶어내면 $$ b_{1} b_{2} \cdots b_{\phi (m)} \equiv a^{\phi (m)} b_{1} b_{2} \cdots b_{\phi (m)} \pmod{m} $$ $\gcd( b_{1} b_{2} \cdots b_{\phi (m)} , m ) =1$ 이므로 양변에서 소거하면 다음을 얻는다. $$ a^{ \phi (m) } \equiv 1 \pmod{m} $$

■