페르마의 소정리

정수 a와 p가 있고 a가 p의 배수가 아니면서 p가 소수(Prime number)일 때 다음이 성립한다.

 

 

수식을 풀이하면 a^p를 p로 나눈 나머지는 a가 된다는 뜻이다.

 

또한 여기서 양변에 a를 나누는 것으로 다음 두 식을 유도할 수 있다.

모듈러 연산은 덧셈, 뺄셈, 곱셈이 가능하다.

 

나눗셈은 불가능하므로