Proof Fermat Little

페르마 소정리 본문 으로 돌아가기

페르마 소정리 : 라이프니쯔 증명에서

a, 2a, 3a , ... , (p-1)a 인 수들을 보자.

어떤 두수도 p로 나눈 나머지가 다르다.

나머지가 같은 두수가 있다고 해보자. ka 와 la 라 하자. $l<k$ 라 하고, 나머지가 같으니,

$ka=pk'+r$

$la=pl'+r$

인, k', l' 가 있기 마련이다. 그렇다면 두 수의 차

$(k-l)a=(k'-l')p$

다. p 는 a 를 나누지 않는다고 문제의 조건에서 말했으므로, p 는 k-1 을 나누어야 한다. 하지만 이것은 불가능하다. k-l 은 p 보다 작으니까. 증명 끝.

증명을 모듈합동 언어로 다시 써본 경우

모둘 p에 대한 합동 관계로 표현하면

$1\cdot 2\cdot 3\cdot 4\cdot 5\cdots (p-1)a^{p-1}\equiv _{p}1\cdot 2\cdot 3\cdots (p-1)$

이므로 $K=1\cdot 2\cdot 3\cdot 4\cdot 5\cdots (p-1)$라 할 때,

$K(a^{p-1}-1)\equiv _{p}0$

이므로 모듈 합동 관계 의 기본 성질 1), 5)와 p가 소수이므로 기본 성질 7)에 따라

$a^{p-1}-1\equiv _{p}0$

증명 끝.

Congruence 개념을 드러내놓고 써서

a 와 b 가 congruent 하면, congruent 한 것들 끼리 곱한 결과들도 congruent 하므로 이것을 조금 유식하게 써주면

$a\equiv _{m}b\ \Rightarrow a^{n}\equiv _{m}b^{n}$

이다. 이것을 안다고 전제한다. 모듈 합동 참고.

페르마 소정리 일반화 1 증명

증명 1 : 페르마 소정리를 이용

p가 a를 나누는 경우와 나누지 않는 두 경우로 나눠 볼 수 있다.

• p가 a를 나눈다면, p는 $a\cdot a^{p-1}$의 앞항 a를 나눈다.
• p가 a를 나누지 않는다면, 페르마 소정리에 따라 p 는 $a\cdot a^{p-1}$의 뒤 항 $a^{p-1}$을 나눈다. 증명 끝.

증명 2 : 수학적 귀납의 원칙

a 를 $1,2,3,\dots$ 으로 하면서 수학적 귀납의 원칙을 써보자.

• a = 1 일 때, 1-1 = 0 이므로 $0=pt$ 인 t 가 존재한다. (물론 이때 자연수를 0까지 확장했다.)
• a = 2 일 때, $2,4,6,\dots ,2(p-1)$ 인 수들을 보자.
  • p 가 2 를 나눈다면 p = 2 이므로 $2^{p}-2$ 는 p 로 나뉜다.
  • p 가 2 로 나뉘지 않는 경우를 보자. 위의 $2,4,6,\dots ,2(p-1)$ 인 수들은 모두 p 로 나눈 나머지가 다르다. 나머지는 라이프니쯔의 증명에서 본 위의 부분과 같이 한다. 그 수들을 모두 곱하면

$2^{p-1}(p-1)!=pN+(p-1)!$

인 자연수 N 이 있을 것이고 따라서

$(2^{p-1}-1)(p-1)!=pN$

이다. p 는 (p-1)! 을 나눌 수 없으므로 $2^{p-1}-1$ 를 나눈다. 따라서 $2^{p}-2$ 도 p 로 나뉜다.

• a가 k 일 때까지 모두 페르마 소정리가 통했다고 보자. 그럴 때 k+1 일 때도 성립한다는 것을 보이면 '수학적 귀납의 원칙'에 따라 증명이 충분하다. 뉴튼의 이항정리에 따라,

$(k+1)^{p}=k^{p}+{\binom {k}{1}}a^{k-1}+\cdots +{\binom {p}{p-1}}k^{1}+1$

이므로

$(k+1)^{p}-(k+1)=k^{p}+{\binom {p}{1}}k^{p-1}+\cdots +{\binom {p}{p-1}}k^{1}-k$

이다. a가 k 일 때까지 모두 페르마 소정리가 통한다고 가정했기 때문에 $k^{p}-k$ 는 p 로 나뉘고, 이항정리의 계수들 ${\binom {p}{i}}$ 들은 i 가 $1,2,\dots ,p-1$ 일 때, 모두 p로 나뉜다.

$(a+1)^{p}-(a+1)=Np$

인 N 이 있을 수 밖에 없다. 증명 끝.

증명 3  : 재미나는 !

뉴튼의 이항정리를 이용하여 다음 항들이 모두 p로 나뉜다는 것을 스스로 보여보라.

$(n_{1}+n_{2})^{p}-(n_{1}^{p}+n_{2}^{p})$

$(n_{1}+n_{2}+n_{3})^{p}-(n_{1}^{p}+n_{2}^{p}+n_{3}^{p})$

$(n_{1}+n_{2}+n_{3}+n_{4})^{p}-(n_{1}^{p}+n_{2}^{p}+n_{3}^{p}+n_{4}^{p})$

...

그리고 $n_{i}$ 에 모두 1을 대입하라.

윌슨 정리의 증명

증명은 두 방향으로 이루어진다.

• $\Rightarrow$  : p 가 소수면, $(p-1)!+1$ 은 p 로 나뉜다.
• $\Leftarrow$ : p 가 소수 아니면, $(p-1)!+1$ 은 p 로 나뉘지 않는다.

$\Rightarrow$

$2,3,4,\dots ,p-2$ 이 수 중 하나를 a 라 하자. 그리고

$a,2a,3a,\dots ,(p-1)a$

라는 수들을 보자. 다음 성질을 스스로 확인하라.

위의 수들은 p 로 나누어 모두 나머지가 다르다.

따라서 나머지는 $1,2,3,\dots ,p-1$ 가 한번씩 나오게 되고, 그 중 p로 나눈 나머지가 1 인 어떤 수 b 가 있을 수 밖에 없다. 이때 b 는 다음 성질을 갖게 된다는 것을 확인하라.

b 라는 수는 1 도, p-1 도 a 도 될 수 없다.

위의 두가지 성질에 따라 다음을 알 수 있다. $2,3,4,\dots ,p-2$ 중 어떤 수 a 를 뽑고 그 수와 곱한 결과를 p 로 나눈 나머지가 1인 b 를 골라낸다. 이 b 는 a 와 다르다. 이제 다른 수에 대해서도 마찬가지 방식으로 해간다. 그런 쌍의 개수는 쌍의 개수는${\frac {p-3}{2}}$ 일 것이다. 이 쌍을 이루는 수들을 모두 곱하면

$2\cdot 3\cdots p-3\cdot p-2$

가 되고, 이 수를 p 로 나누면 나머지가 1 이다. 그리고 p-1 을 p로 나눈 나머지는 -1 이다. 따라서

$(p-1)!$ 을 p 로 나눈 나머지도 -1 이다.

따라서 $(p-1)!+1$ 은 p 로 나뉜다. 증명 끝.

$\Leftarrow$

p 가 소수가 아니라고 가정했으므로, 어떤 소수 q 에 대해

p = qt

인 t 가 있다는 말이다. 이때 $q<p$ 이므로,

$1\cdot 2\cdot 3\cdots p-2\cdot p-1=(p-1)!=qs$

인 s 가 있을 수 밖에 없다. 따라서 양쪽 항에 모두 1 을 더한 결과 (p-1)! + 1 은 p 로 나뉠 수 없다. 만약 나뉜다면 그것은 qs + 1 이 나뉜다는 뜻이 되고, 그것은 qs +1 = pn 인 n 이 있다는 말이다. 이는

qs + 1 = qtn

이고 q (tn -s ) = 1 이다. 말이 안된다.

문제들 해설

(문제 1) $7^{222}$의 십진법으로 나타낼 때 끝자리수는 무엇일까?

$7^{222}$을 10으로 나눈 나머지를 찾으면 된다. 7과 10은 서로소 관계이고 $\varphi (10)$은 4이므로 오일러 정리에 따라 $7^{4}\equiv _{10}1$ 이고 $220=4\cdot 55$다. 따라서 $7^{4\cdot 55}\equiv _{10}1$ 이므로 $7^{2}\equiv _{10}49\equiv _{10}9$ : 답은 9

Note

Math : Math글쓰기 | Math번역 | MathBoard | Math&Culture | MathMoim
OnLineMathCenter | MathCamp | SoftMathJournal | MathBook | CyberAcademia | Academia