[정수론](-)[e_m(a)가 ϕ를 나누는가]

ϕ = em(a)k + r이라고 하고
위수의 성질로 r이 0임을 보이자
-> 위수가 ■을 나누는가에서도 응용 가능

서로소인 정수 a와 m에 대해서 a^e ≡ 1 (mod m)을 만족하는 가장 작은 지수 e ≥ 1을 em(a)라고 정의하고 법 m에 대한 a의 위수(order of a modulo m)라고 부른다. em(a)가 항상 ϕ(m)의 약수임을 증명하여라.

ϕ(m) = em(a)k + r 라 두자.
{0 <= r < em(a)}
r = 0임을 보이면 e | ϕ(m)를 보일 수 있다.

 

gcd(a, m) = 1 이므로, 오일러 공식에 의해,
a^ϕ(m) ≡ a^(em(a) * k + r) ≡ 1 (mod m)
이때, 위수의 정의에 의해 a^em(a) ≡ 1 (mod m) 이므로,
a^em(a) * k ≡ (a^em(a))^k ≡ 1^k ≡ 1 (mod m)
따라서 a^(em(a) * k + r) ≡ a^r ≡ 1 (mod m)

 

만약 0 < r < em(a)라면?
    a^■ ≡ 1 (mod m) 을 만족하는 더 작은 수 r이 나오므로 모순
따라서 r = 0이다.

 

따라서 ϕ(m) = em(a)k 이므로
em(a) | ϕ(m)