Fermat's Little Theorem. p가 소수이고, a가 a가 p로 나누었을 때 나누어 떨어지지 않는 수라면,
a^(p -1) ≡ 1 (mod p)
위 식이 성립한다.
페르마 본인은 이 정리의 증명을 쓰지 않았지만, 이 정리의 증명은 어렵지 않다. 먼저, p로 나누어 떨어지지 않는 수는, p가 소수일 때 p - 1만큼 존재한다. 또, 재미있는 사실은 1에서 p - 1까지의 수를 p로 나누었다면, 여기에 어떤 수를 곱하더라도 그 나머지는 이 집합에 포함된다. 이것을 다시 쓰면,
1, 2, 3, ... (p - 1) (mod p)는, a, 2a, 3a, ... (p - 1)a (mod p)와 합동이다.
즉, 1, 2, 3, ... (p - 1) (mod p) ≡ a, 2a, 3a, ... (p - 1)a (mod p)
이 수들을 곱해보면,
a^(p - 1)(1 * 2 * 3 * ... (p - 1)) ≡ (1 * 2 * 3 * ... * (p - 1)) (mod p)
a^(p - 1)(p - 1)! ≡ (p - 1)! (mod p),
a^(p - 1) ≡ 1 (mod p)의 결과를 얻게 된다.
이 정리가 성립하는 중요한 이유는, 위에서 봤듯이 1부터 p - 1사이의 어떤 수도 7로 나누더라도 1 이외의 공통 인수가 없기 때문에, 나머지는 언제나 동일한 집합이라는 점이다. 이 증명 방법의 발상은 오일러 정리를 이해하는데도 도움이 된다. 여기서 말하는 오일러 정리란 다음을 말하는데,
Euler's Theorem. gcd(a, n) = 1일 때, a^Φ(n) ≡ 1 (mod n)
오일러 정리의 증명 방법은, 페르마의 소정리를 증명하는 방법과 거의 동일하다. 먼저, Φ 함수의 정의를 살펴보면, gcd(a, n) = 1의 관계가 있을 때, Φ(n) = #{a : 1 ≤ a ≤ n}이다. 왜 gcd(a, n) = 1의 관계가 필요한가? 이것은, 페르마의 소정리 a^(p - 1) ≡ 1 (mod p)에서 p가 소수이면서, a를 p로 나누었을 때 나누어떨어지지 않는 수가 되어야 하는 것과 마찬가지 이유이다. 즉, 동일한 나머지 집합을 가지기 위해서이다.
이제, 현실적으로 Φ(n)의 값을 어떻게 알아내야 할까? 먼저, 어떤 수라도 소수의 곱으로 표현할 수 있기 때문에, n은, p^k의 형태로 나타낼 수 있다. 두 수가 소수라면 Φ(pq) = Φ(p)Φ(q)의 형태로 쓸 수 있기 때문이다. 이제, 문제는 Φ(p^k)를 어떻게 계산하는가로 바뀌었다.
Φ(n)의 정의를 다시 살펴보자. Φ(n) = #{a : 1 ≤ a ≤ n, gcd(a n) = 1}, 즉 a와 n 사이에서 서로소인 수의 개수이다. 예를 들어, Φ(6)은, 1, 5가 6과 서로소이므로 Φ(6) = 2, Φ(7)은 7과 서로소인 수가 1, 2, 3, 4, 5, 6이므로 6이다. 그렇다면, Φ(p^k)의 경우에는, p^k의 수 중에서, a가 p로 나누어 떨어지는 수를 모두 제외한다면, Φ(p^k)를 구할 수 있지 않을까? 그럼, 1 ≤ a ≤ p^k의 수에서 p로 나누어 떨어지는 수는 무엇인가? 그 수는,
p, 2p, 3p, 4p, 5p, ... (p^(k - 1) - 2)p, (p^(k - 1) - 1)p, p^k
이며, 모두 p^(k - 1)개 존재하게 된다. 예를 들어 생각해보라. 2^8 = 256이며, 이 중에서 2로 나누어 떨어지는 수는 1 * 2, 2 * 2, 3 * 2, 4 * 2, ... 127 * 2, 128 * 2이다. 즉, 1부터 128까지, 2^(8 -1)만큼 존재한다. 따라서, Φ(p^k) = p^k - p^(k - 1)이다.
Φ(n)을 계산하는데, n이 소수 p라면 어떻게 되는가? 이 경우는, Φ(p) = p - 1이며, Φ(pq) = (p - 1)(q - 1)이 성립한다.
Library/Mathematics