pepan  페르마(Fermat) 수 Fn=22n+1 가 소수일지 어떨지를 판정한다

int pepan(int n);

n  페르마수에 있어서의 정정수

소수라면 1, 비소수(즉, 합성수)라면 0, 내부 에러가 일어났다
때는 -1.

(은)는 소수여도 예상했다. 이 수는, n = 5, 6, 7, 8, ... 에 응해 매우 빠르고 터무니없게 커진다. 따라서 컴퓨터 없음의 시대에는, 이러한 값을 계산하는 것은 거의 불가능했다. 확실히,

F₀ = 3 F₁ = 5 F₂ = 17 F₃ = 257 F₄ = 65537

(은)는 소수이다. 그러나, 나-(1732년)에 의해

F₅ = 2³²+1 = 4294967297 = 641 x 6700417

(은)는 합성수인 것이 후 정원 샀다.

본함수에서는 페판의 판정법을 이용해, 페르마수가 소수일지 어떨지를 조사한다. 페판의 판정법에 의하면, n 가 1 이상 때

3 ^{(F_n-1) / 2} ≡ -1 (mod F_n)

(이)가 성립되는 것이 F_n 가 소수이기 위한 필요 충분조건이다.

지금의 컴퓨터 시대로는, 많은 사람들의 노력에도 불구하고, F₄ 보다 큰 소수는 1개도 발견되지 않았다. 덧붙여 페르마수가 합성수의 경우, 그 소인수는 모두

k 2^m+1 (m≥n+2)

의 형태를 하고 있다.

여담이 되지만, 소수가 되는 페르마수(페르마 소수)를 찾아내는 것은 왜 그렇게 중요한가라고 하면(자), 1개(살)에는, 전혀 관계가 없을 것 같은 기하학의 정다각형의 작도 문제와 깊은 관계가 있는 것을 Gauss가 발견했기 때문에이다.

Gauss는, n 의 값이

·2 의 베키이다
·페르마 소수이다
·이러한 2 종류의 수의 적이다

때에, 한편 그 때에만, 정 n 각형은 자와 컴퍼스로 작도 가능하다 일을 증명했다. Gauss의 묘석에 새겨진 정 17 각형은, 정확히 페르마수 F₂에 대응하는 것이다. 따라서 작도 가능한 홀수 정다각형은 페르마 소수부터,

정 3 각형, 5 각형, 15 각형, 17 각형, 51 각형, 85 각형,...

등의 보고된다.