8.4 소수 또는 합성수?

congruences의 마지막 응용으로 큰 수가 소수인지 합성수인지 검사하는 방법에 대해서 공부해보자. 그것은 임의의 수 중 어떤 수를 조사하는데 매우 능률적인 방법이고, 가장 좋은 일반적인 방법이다. 그것은 95쪽에 나오는 페르마의 congruence에 기초하고 있다.

우리가 조사해야 할 수를 N이라고 하자. N에 비해 상대적으로 작은 소수를 a라고 하자. a는 N을 나누지 않는 작은 소수로 정하면 편하다. 예를 들어서, a는 2, 3, 5. 만약 N이 소수라면 페르마의 congruence에 따라[eqn: a ^{N-1```}==1(mod N)]을 만족할 것이다. 결과적으로, 만약 이 congruence를 검사해보고 그 식이 만족하지 않는다면 N은 합성수이다.

예를 들어서 N=91, a=2의 경우에 대해서 생각해보자.

그 때,

[eqn: a ^{N-1} =2 ^{90} =2 ^{64} ․2 ^{16`}․ 2^8 ․2^2]

더구나,

[eqn: 2^8 =256 ==-17(mod91)]

[eqn: 2^16 = (2^8 )^2 ==(-17)^2 =289 ==16 (mod91)]

[eqn: 2^32 =( 2^16 )^2 = (2^8 )^2 ==(16)^2 =256 ==-17(mod91)]

[eqn: 2^64 = (2^32 )^2 ==(-17)^2 =289 ==16 (mod91)]

따라서

[eqn: 2 ^{90} =2 ^{64} ․2 ^{16`}․ 2^8 ․2^2]

[eqn: ==16․16․(-17)․4==64not==1(mod91)]

N은 합성수이다. 사실 [eqn: 91=7․13] 이다.

위의 예제는 그 방법의 참된 힘을 보여주기에는 너무 간단하다. 적절한 컴퓨터 프로그램은 매우 큰 수가 합성수임을 보이는 것을 가능하게 한다.

불행히도, 그 방법은 인수를 지정할 수 없다. 따라서 그 수가 소수인지, 아님 아직 그것의 소수가 있을지도 모르겠다는 것을 넌지시도 알 수 없다.

다음은 2.3절에서 논의했던 페르마 수이다.

[eqn: F_n = 2^2^n +1]

n이 0, 1, 2, 3, 4 일 때, [eqn: F_n]은 소수임을 알고 있다.

n이 5일 경우에 대해서 알아보자.

[eqn: f_5 = 2 ^2^5 +1 = 2^32 +1 = 4294967297]

페르마의 congruence에 의해 a를 3으로 하자. 만약 [eqn: F_5] 가 소수라면

[eqn: 3^2^32 ==1 (mod F_5 )].

좌변에 있는 수를 계산하기 위해서 32번 곱해야 하고, 각각의 단계에서 [eqn: mod F_5] 에 대한 나머지가 나올 것이다. 계산해보면 [eqn: 3^2^32 not==1 (mod F_5 )]이다. 따라서

[eqn: F_5]는 합성수이다. [eqn: F_5]는 641을 인수로 가진다. 똑같은 방법은 더 큰 몇몇의 페르마수가 소수가 아님을 보이기 위하여 사용되어왔다.  그 수들 중 인수를 아는 것도 있고 모르는 것도 있다.

만약 N과 소수 a가 주어지고 [eqn: a ^{N-1```}==1(mod N)]을 만족한다고 해도 N이 소수일 수도 있고 합성수일 수도 있다. N이 합성수일 때 그 식을 만족하는 것은 예외이고 대부분 그 식을 만족하면 N을 소수라고 생각한다.  그러나, 명확히 알고 싶을 것이다. 이것은 소수N이 [eqn: a ^{N-1```}==1(mod N)]을 만족하면서 N-1의 약수가 아닌 경우를 상세히 논술함에 의해 완성될 수 있다.

다른 접근도 있다.  그 때는 N이 너무 크지 않아야 효과적이다.  a=2라고 하자. Poulet과 Lehmer는 N이 100000보다 작거나 같은 경우에 대해서 [eqn: 2 ^{N-1```}==1(mod N)]다 계산했다. 그 중 [eqn: 2 ^{N-1```}==1(mod N)]을 만족하는 합성수인 N을 때로는 가짜의 소수(카마이클 소수)라고 부른다. 이러한 수 N은 또한 최대 소수 인수를 가진다.

Poulet과 Lehmer의 표에 의하면 N이 100000000이 작거나 같은 경우에 대해서 소수성을 결정할 수 있다. 첫째로 [eqn: 2 ^{N-1```}==1(mod N)]을 만족하는지 조사해야한다.  만약 만족하지 않는다면 N은 합성수이다. 만약 congruence를 만족하고 N이 표에 있다면 그때 또한 N은 합성수이다. 그리고 표로부터 소수 인수를 알 수 있다. 마지막으로 만약 [eqn: 2 ^{N-1```}==1(mod N)]을 만족하고 N이 표에 없다면 N은 소수이다.

[eqn: 2 ^{N-1```}==1(mod N)]을 만족하는 가장 작은 합성수 N은 341이다.

즉, N=341=11․31.

1000이하의 두 수에 대해서 살펴보자.

N=561=3․11․17

N=645=3․5․43

N=561은 주목할 만하다. 모든 정수 a에 대해서 [eqn: a ^{N-1```}==1(mod N)]을 만족한다.  그러한 특별한 수는 페르마 property를 가진다. 그러한 수에 대한 연구가 많이 되어져왔다.  D.H.Lehmer의 논문과 표에서 이러한 수들을 볼 수 있다. 수정리의 표를 참고하라.