위키득계정 ↗
과학

페르마의 소정리

페르마의 소정리과학
영문명
Fermat’s little theorem
법의 조건
p는 소수
모든 정수 a
aᵖ≡a (mod p)
p가 a를 나누지 않을 때
aᵖ⁻¹≡1 (mod p)
페르마의 소정리는 소수 p와 정수 a에 대해 aᵖ≡a (mod p)가 성립한다는 정리다. a가 p의 배수가 아니면 aᵖ⁻¹≡1 (mod p)로도 나타낼 수 있다.

서로 다른 두 표현

aᵖ≡a라는 식은 a가 p의 배수여도 성립한다. 반면 지수가 p−1이고 오른쪽이 1인 식에는 p가 a를 나누지 않는 조건이 필요하다. 법 p에서 0인 값을 무조건 약분해서는 안 된다.

거듭제곱 계산

법 7에서 3⁶≡1이다. 100=6×16+4이므로 3¹⁰⁰≡3⁴≡4 (mod 7)로 계산할 수 있다. 지수를 줄이는 과정은 정리의 조건과 p−1이라는 주기를 근거로 한다.

역원에 연결

소수 p에 대해 a가 p의 배수가 아니면 a×aᵖ⁻²≡1 (mod p)다. 따라서 aᵖ⁻²은 a의 모듈러 역원을 나타낸다. 합성수 법에 소수의 공식을 그대로 적용하지 않는다.

소수 판정의 한계

어떤 밑에서 aⁿ⁻¹≡1 (mod n)이 성립해도 n이 반드시 소수는 아니다. 341=11×31은 합성수지만 2³⁴⁰≡1 (mod 341)이다. 정리의 결론 하나를 통과했다는 사실과 소수임을 증명했다는 사실은 다르다.

관련 문서

소수 (수론) / 합성수 / 합동식 / 거듭제곱 / 모듈러 역원 / 서로소 / 나머지 / 소인수분해