7.5 Fermat's congruence

이항정리에서

(7.51)

일반적으로

(7.52)

처음과 마지막 계수는 1이다. 가운데 이항계수는

(7.53)

일반적으로

(7.54)

이 계수들은 (7.51)에서  의 연속적인 곱에 의해서 나온 것이기 때문에 분명히 정수이다.

이제  가 소수라고 가정하자. (7.54)의 정수를 정수의 형태로 쓰기 위하여는 우리는 분모  와 분자  에 공통인수를 약분하여야 한다. 그러나 분모에는 소인수  가 없다. 따라서 약분 후에도 분자에  는 남아있다. 결론을 내리면

가 소수라면 (7.52)에 있는모든 이항 계수들은( 첫 번째와 마지막을 빼고) 모두 에 의해서 나누어진다.

이제 (7.52) 에 있는 와  가 정수라고 하자. 만약 우리가 (7.52) 에 있는 식을 congruence(mod ) 로 본다면 우리는 결론지을 수 있다.

정수  와  그리고 소수  에 대하여

(7.55)        (mod )

예를 들어  에 대하여

모든 가운데 계수들이 5에 의하여 나누어 지므로 우리는 (7.55)와 같이

(mod 5)  임을 알 수 있다.

우리는 (7.55)로부터 중요한 결과를 얻어낼 수 있다. 먼저  을 적용하자. 그러면

(mod )

다음으로  이라 하자 그러면

(mod )  따라서   (mod )

다음으로  이라 하면, 우리는   (mod ) 를 얻는다.

이러한 과정으로 우리는

(7.57)      에 대해서

(mod )를 증명할 수 있다.

과  인 경우는 분명하다.  모든 수는  (7.56)에 있는 나머지의 하나와 congruent(mod ) 이므로 우리는 다음과 같은 결론을 내릴 수 있다.

모든 정수  와 모든 소수 에 대하여

(7.57)      (mod )

이  congruence law를 페르마 정리라고 부른다.어떤 사람들은 5.3절에 있는 페르마의 마지막 정리 또는 페르마 conjecture 와 구별하기 위하여 little  Fermat's theorem 이라고 부른다.

(예) ,  에 대하여     ,  이므로               이것은   Fermat's congruence 와 일치한다.

canceiiation law (7.3절) 에 의해서  와 가 서로 소라면  (7.57) 에 있는  Fermat's congruence의 양변에서 공통인수  를 소거할 수 있다. 이것은 다음과 같은 결과가 된다.

만약 가 정수이고 소수 에 의하여 나누어지지 않는다면

(7.58)       ( mod  )

이 결과는 페르마 정리로 알려져 있다.

(예) ,   일 때

,                            ,             ,    이므로

이것은 (7.58) 의  Fermat's congruence 와 일치한다.

(7.58) 의  Fermat's congruence 의 적용으로 우리는 5장에서의 피타고라스로 돌아가 다음을 증명할 수 있다.

피타고라스 삼각형의 변들의 곱은 60에 의해서 나누어진다.

(증명) 이것은 primate triangle 에 대하여 증명하는 것으로 충분하다.

(5.27)에 의하여  그 곱은   이다.

가 60에 의하여 나누어진다 와  가 4와 3가 5로 나누어진다는 것이다 는 것은 필요충분조건이다.   둘 중 하나는 짝수이므로 ,  은 4로 나누어지며 따라서  는 4로 나누어진다.  둘 중 적어도 하나가 3으로 나누어지면 는 3으로 나누어진다.

;만약 둘 다 3으로 나누어지지 않는다면 (7.58)에 의해서  ,  이므로

,

따라서

같은 방법으로  는 5로 나누어진다. 이것은  또는  이 5로 나누어지면 분명하다. 둘 다 나누어지지 않는다면 다시  (7.58) Fermat's congruence 에 의해서