페르마의 소정리

[1. 정의]

1. p 가 소수이고, (prime number) , a 가 정수일 때
   # a^p ≡ a (mod p)
   # a^p 를 p 로 모듈러 연산을 할 경우, 그 나머지는 a 이다.
   
   
2. 특히, p 가 소수이고, a 가 p 의 배수가 아닐 때 (a 와 p 가 서로소 일 때)
   # a^(p-1) ≡ 1 (mod p)
   # a^(p-1) 을 p 로 모듈러 연산 한 경우, 그 나머지는 항상 1 이다.

---

[2. 활용]

2번 정의에서, 양변(?) 에 a^-1 을 곱하면, 아래와 같은 식이 성립한다.

• 모듈러 연산 역원(?) 

a^(p-2) ≡ a^-1 (mod p)

• 즉, a^-1 mod p = a^(p-2) mod p 이다.