페르마의 소정리

IT 위키

페르마의 소정리(Fermat's little theorem, 小定理)는 정수론에서 소수와 모듈러 산술의 관계를 설명하는 기본적인 정리로, 소수 p와 정수 a가 서로소일 때 ap−1 ≡ 1 (mod p)라는 형태로 표현된다. 이 정리는 모듈러 연산에서의 지수 계산을 단순화하며, 오일러 정리의 특수한 형태로 볼 수 있다.

1 정리 내용[편집 | 원본 편집]

정수 a가 소수 p와 서로소일 때 다음이 성립한다. ap−1 ≡ 1 (mod p)

또한, 일반화된 형태로 다음과 같이 표현되기도 한다. ap ≡ a (mod p) 이 식은 a가 p로 나누어떨어지지 않더라도 항상 성립한다.

예:

  • a = 2, p = 7인 경우: 26 = 64 ≡ 1 (mod 7)
  • a = 10, p = 13인 경우: 1012 = 1000000000000 ≡ 1 (mod 13)

2 조건[편집 | 원본 편집]

  • p는 소수여야 하며
  • a는 p와 서로소여야 한다 (즉, gcd(a, p) = 1)

단, 일반화된 형태 ap ≡ a (mod p)는 a가 p의 배수여도 성립한다.

3 오일러 정리와의 관계[편집 | 원본 편집]

페르마의 소정리는 오일러 정리의 특수한 경우이다. 오일러 정리는 다음과 같이 일반화되어 있다: aφ(n) ≡ 1 (mod n), 단 a와 n은 서로소

여기서 n = p (소수)이면 φ(p) = p − 1이므로, ap−1 ≡ 1 (mod p)가 되어 페르마의 소정리와 일치한다.

4 증명 개요[편집 | 원본 편집]

페르마의 소정리는 다음과 같은 방식으로 증명할 수 있다.

  • 정수 a가 p와 서로소일 때, a, 2a, 3a, ..., (p−1)a를 mod p로 나타낸 결과는 1, 2, ..., (p−1)의 순열이 된다.
  • 양변의 곱을 비교하면 ap−1(p−1)! ≡ (p−1)! (mod p)가 되며,
  • p는 소수이므로 (p−1)!은 p와 서로소이며, 양변을 약분하면 ap−1 ≡ 1 (mod p)가 된다.

5 응용[편집 | 원본 편집]

  • RSA 암호 알고리즘의 이론적 배경으로 활용된다.
  • 소수 판별 알고리즘(예: 밀러-라빈 검사)의 기본 원리로 사용된다.
  • 모듈러 연산에서 거듭제곱 계산을 단순화하는 데 유용하다.

6 같이 보기[편집 | 원본 편집]

7 참고 문헌[편집 | 원본 편집]

  • G. H. Hardy and E. M. Wright, *An Introduction to the Theory of Numbers*, Oxford University Press, 2008.
  • Kenneth H. Rosen, *Elementary Number Theory and Its Applications*, Pearson, 2010.

8 각주[편집 | 원본 편집]