Fermat’s Little Theorem   페르마 소정리

1. 페르마의 소정리 (Fermat's Little Theorem)

  ㅇ p가 소수이고, a와 p가 서로소이면, 
     -  ap-1 ≡ 1 (mod p)
  
  ㅇ 즉, 
     - ap-1를 소수 p로 나누면, 나머지가 1이 됨
     - 어떤 수 a가, (p-1)의 거듭제곱이 되어야 만, 법 p에 대해 1과 합동이 됨

  ※ 피에르 페르마 (Pierre de Fermat, 1601~1665) : 17세기 프랑스의 수학자


2. 오일러의 정리 

  ㅇ 페르마의 소정리를 일반화한 것

  ㅇ 자연수 n에 대해, a와 n이 서로소이면, 즉 a와 n의 최대공약수가 1이면,
     -  aф(n) ≡ 1 (mod n) 

  ㅇ 여기서, ф(n)은,
     -  1부터 n까지의 수 중에, n과 서로소인 자연수의 개수를 지칭하는 오일러 파이 함수