페르마의 작은 정리는 정수 모듈로 소수의 계산 능력을 제공하는 기본 정수 이론의 기본 정리입니다. 오일러 정리의 특정 사례이며 소수 테스트 및 공개 키 암호화와 같은 기본 정수 이론의 적용에 필수적입니다. 이것을 페르마의 작은 정리라고 합니다.
페르마의 정리는 페르마의 작은 정리라고도 하며, P는 소수이고 'a'는 P로 나눌 수 없는 양의 정수입니다. 그러면 -
a P−1 ≡ 1 모드 P
두 번째 조건은 P가 소수이고 a가 정수이면 a P 입니다. ≡ 1 모드 P.
증거 - Zp 모듈로 P를 곱할 때 정수 {0, 1…P-1}의 집합입니다. 결과는 Zp의 모든 요소를 포함합니다. 어떤 시퀀스에서 ax 0 ≡ 0 mod P. 따라서 (P-1) 숫자 {a mod P, 2a mod P,…((P-1) a mod P)}는 숫자 {1, 2 ,…(P-1)} 어떤 순서로.
두 단계에서 숫자를 곱하고 결과 모드 P를 취하면
에이 x 2 에이 x .... x ((P-1)a)=[(a mod P) x (2a mod P) x … x ((P-1) 모드 P)] 모드 P
=[1 x 2 x… x (P-1)] 모드 P
=(P-1)! 모드 P
하지만
a x 2a x…x ((P-1)a) =(P-1)!a P−1
(P-1)! a P−1 ≡ (𝑃 − 1)! 모드 P
a P−1 ≡ 1 모드 P
p보다 작은 양의 정수 집합:{1, 2... p1}을 고려하고 각 요소에 a, modulo p를 곱하여 집합 X ={a mod p, 2a mod p를 받습니다. . . (p1) 모드 p}. p가 a를 나누지 않기 때문에 X의 어떤 요소도 0과 유사하지 않습니다.
또한 X의 정수 중 두 개는 동일하지 않습니다. 이것을 보려면 1 ≤ p1인 경우 (ja ≡ p)를 고려하십시오. p이기 때문에 방정식의 양변에서 삭제할 수 있으므로 − j≡ p)가 됩니다.
이 최종 유사성은 j와 k가 모두 p보다 작은 양의 정수이기 때문에 액세스할 수 없습니다. 따라서 X의 (p1) 요소는 동일한 두 요소가 없는 모두 양의 정수임을 이해해야 합니다.
수치 - 페르마의 정리에 따르면 p가 소수이고 a가 P로 나눌 수 없는 양의 정수이면 a P−1 ≡ 1(모드 p).
따라서 3 10 ≡ 1(모드 11).
따라서 3 201 =(3 10 ) 20 x 3 ≡ 3(모드 11).
Fermats little theorem은 때때로 일부 지수에 대한 솔루션을 빠르게 찾는 데 유용합니다. 다음 예는 개념을 보여줍니다.
예시 1 − 6 10 의 결과 찾기 모드 11.
해결책
여기에 6 10 이 있습니다. mod 11 =1. 이것은 p =11인 페르마의 작은 정리의 첫 번째 버전입니다.
예시 2 − 3 12 의 결과 찾기 모드 11.
해결책
따라서 지수(12)와 계수(11)는 같지 않습니다. 대입으로 이것은 페르마의 작은 정리를 사용하여 정의할 수 있습니다.
3 12 mod11 =(3 11 x3)mod11 =(3 11 mod11)(3 mod11) =(3x3)mod11 =9