페르마 소정리와 오일러 정리는 내용도 비슷하고 그 증명법도 비슷합니다.
그러므로 이번 글에서 이 두가지 정리를 함께 증명해보도록 하겠습니다.
페르마의 소정리
이제 페르마의 소정리를 보겠습니다.
"p가 소수이고 a가 p의 배수가 아닐 때(서로소일 때)"
이다
증명
이를 증명하는 굉장히 쉬운 증명이 있습니다.
그것은 바로 '기약잉여계'를 이용한 증명입니다.
기약잉여계는 어떤 자연수 n이 있을 때 n보다 작으면서 n과 서로소인 수들의 집합을 말합니다.
소수 p가 있을 때 p의 기약잉여계 M은
M = {1,2,3, ... ,p-1}
일 것입니다.
이때 M의 원소들은 모두 p와 서로소이므로 M을 모두 곱한 S1 = 1X 2 X 3 X ... X (p-1) 또한 p와 서로소일 것입니다.
또한 p의 배수가 아닌 어떤 숫자 a를 M과 곱한다고 하면
aM = {a,2a,3a, ... ,a(p-1)}
입니다.
이때 a는 p와 서로소이므로 aM의 원소들을 모두 곱한 S2 = a X 2a X 3a X ... X a(p-1) 도 p와 서로소입니다.
여기서 다음과 같은 식이 성립합니다.
예를 들어 n = 7이고 a = 2 이라고 하면 M과 aM과 S1과 S2는 각각 다음과 같을 것입니다.
M = {1,2,3,4,5,6} , aM = {2,4,6,8,10,12} = {2,4,6,(7+1),(7+3),(7+5)}
S1 = 6! S2 = 6! + x*7 + y * 7^2 + z*7^3
이때 S2의 7이 인수로 들어간 항들은 모듈러 7에서 의미가 없으므로 S1과 S2는 모듈러 7에서 서로 같습니다.
이는 귀류법을 통해 증명할 수 있습니다.
만일 M과 aM이 모듈러 p에서 서로 다르다면, aM의 원소들의 모듈러 p를 구했을 때 그 값들이 모두 서로 다르면서 p와 서로소이야 합니다.
일단 M의 원소들은 p와 서로소이고, a도 p와 서로소이므로 그 값중에 p와 서로소가 아닌 경우는 없을 것입니다.
그러나 그 값들 중 서로 같은 경우가 있을지는 모릅니다.
M의 원소 i, j(1 ≤ i < j ≤ p-1)가 있어서 ai = aj (mod p)인 경우가 있다고 합시다.
a는 p와 서로소이므로 양변에서 지울 수 있습니다.
그렇다면 i = j (mod p) 라는 의미인데, i와 j는 서로 같을 수 없습니다.
따라서 M과 aM이 서로 다르다는 가정을 했을 때 모순이 생기므로 M = aM (mod p) 가 증명되었습니다.
이어서 페르마의 소정리를 증명하겠습니다.
M은 p와 서로소이므로 역원을 가질 수 있습니다. 따라서 양변에서 M을 지우면
이 됩니다. p-1은 Φ(p)라고 앞에서 언급하였으므로 위 식은
이 되어 우리가 증명하려는 등식을 구할 수 있습니다.
오일러의 정리
"p와 a가 서로소인 양의 정수일 때"
페르마의 소정리는 p가 소수인 특수한 경우를 다루었지만 오일러의 정리는 p가 양의 정수인 일반적인 경우를 다루었습니다.
페르마의 소정리에 대한 증명을 이해하셨으면 오일러의 정리에 대한 증명도 눈감고 하실 수 있으실 겁니다.
증명
이번엔 p가 아닌 Φ(p)의 기약잉여계 M을 구해봅시다.
M = {1,2,3, ..., Φ(p)}
이번에도 M에 p와 서로소인 a를 M에 곱합니다.
aM = {a,2a,3a, ..., aΦ(p)}
이때 마찬가지로 다음과 같은 식이 성립합니다.
M은 p와 서로소이므로 양변에서 지울 수 있으므로
이렇게 오일러의 정리에 대한 증명도 끝났습니다.
이상 글을 마칩니다.