[정수론] 페르마의 작은 정리 (Fermat's Little Theorem)
Math/Numbers/Combinatorics2011. 1. 11. 18:18 |다음은, 중등부 수학경시를 준비해본 사람이면 누구나 친숙한 페르마의 정리 중 하나이다. 나는 뒤늦게 중3때에서야 피타고라스 정리에 뻑이 간 후 수학에 재미를 붙인 케이스라, 그 수학경시에 나가보진 못했다. 기억하기로 재능교육인가에서 김옥경인가? 암튼 이름만 들으면 동네아줌마스러운 아줌마가 쓴 책이 상당히 인기였던걸로 기억한다. 고딩때 친구가 보는걸 잠깐 봤었는데, 상당히 흥미로운 내용이 많았던걸로 기억된다.
테스트 부터 해보자.
증명.
증명방법은 여러가지가 있다. 합동이론, 군론, 수학적귀납법 등등...
암튼, 이 정리는, 페르마의 마지막정리라고 불리는 무지막지한 악명에 눌려, 소정리로 불린다. 그것은 일단 말로쓰면 다음과 같다.
어떤 정수 a 에 대해, 그것이 어떤 소수(prime number) p 로 나누어 떨어지지 않는다면, a p-1 을 p 로 나눈 나머지는 1 이다.
테스트 부터 해보자.
소수로 우선 13 을 선택하고... 피제수로 6 선택하자. 그러면 6 은 13 으로 나누어떨어지지 않으니까, .. 위의 주장 대로라면,
6 의 12 승을 13 으로 나눈 나머지는 1 이어야 한다.
실제로 6 의 12 승은 2176782336 이고, 13 으로 나누면, 몫이 167444795 이고 , 나머지가 1 이다.
증명.
증명방법은 여러가지가 있다. 합동이론, 군론, 수학적귀납법 등등...
여기서는 합동이론으로 증명하도록 한다. 합동에 대한 간단한 개념은 여기를 참조한다. => http://sciphy.tistory.com/363
우선 다음의 보조정리 (lemma ) 부터 증명하자.
lemma) ca ≡ cb ( mod p ) 에서, 소수 p 가 c 를 나누지 않으면, a ≡ b ( mod p ) 이다.
lemma 의 증명) c(a - b) = pk 와 p 가 c 를 나누지 않으면, p 가 소수이므로, p 와 c 는 서로소이다. 즉, 어떤 x , y 에 의해, px + cy = 1 이다.
c(a - b) = pk 의 양변에 y 를 곱하면... cy(a-b) = pky = (1-px)(a-b) = (a-b) - px(a-b)
그러므로, (a-b) = p [ ky + x(a-b) ] 따라서, p | (a-b) , 즉, a ≡ b ( mod p ) 이다.
이제 원래의 정리를 증명해보자.
1 부터 p-1 까지의 집합 A = { 1, 2, ... , p-1 } 를 생각하자.
여기서, 모든 원소에 a 를 곱한 집합 B = { a , 2a , ... , (p-1) a } 를 생각하자.
이제, 이 집합의 원소들이 p 에 대해 모두 서로 다른 0 아닌 나머지를 갖는 다는 것을 보인다면,
B의 원소를 전부곱한것의 p 에 대한 나머지가 전부곱한것의 나머지가 A 의 원소를 모두 곱한 나머지와 같게 될 것이다.
그러면 a p-1 (p-1)! ≡ (p-1)! (mod p ) 가 되고, (p-1)! 은 p 로 나누어떨어지지 않으므로,
lemma 에 의해 양변을 , (p-1)! 로 약분하면, 원하는 정리 a p-1 ≡ 1 (mod p ) 를 얻는다.
따라서, 우리에게 남은 일은 집합 B 의 모든 원소들이 p 에 대해 모두 서로다른 0 아닌 나머지를 갖는다는 것을 보이는 것이다.
이는 귀류법으로 간단히 증명된다.
A 의 서로다른 두 원소를 r , s 라고 하자. 그러면, r 과 s 는 p 에 대해 서로 다른 나머지를 갖는다 .
만약 그에 대응되는 B 의 두원소 ra 와 sa 가 같은 나머지를 같는다면, ra ≡ sa ( mod p ) 이고, p 가 a를 나누지 않는다고 했으므로,
lemma 에 의해, r ≡ s ( mod p ) 이 된다. 이는 r 과 s 가 p 에 대해 다른 나머지를 갖는다고한 가정에 모순이다. 따라서 증명이 완료된다.
그러므로...