[정수론] 페르마의 작은 정리(Fermat's Little Theorem)

페르마의 작은 정리1)p가 소수이고 gcd(a,p)=1 이면, ap-1≡1 (mod p) 이다.2) p가 소수이면 ap≡ a (mod p)이다.1) 증명먼저 complete residue system에 대해 알아야한다. a의 complete residue system은 집합인데 그안에 모든 원소들이 mod a에서 서로 incongruent하고 원소의 개수가 a개인 집합이다. 즉 예를 들어 5의 complete residue system은 {1,2,3,4,5}, {-3,-2,-1,0,1},{10,16,12,23,29} 등이 있다. 이 때 연속적인 a개의 수는 complete residue system이 됨을 확인할 수 있고, {0,1,2,3,4} 와 같은 집합을 the least complete residue system 이라고 한다.만약 a*k ≡ a*j mod p 라면 gcd(a,p)=1이므로 k ≡ j mod p 가..........

원문링크 : [정수론] 페르마의 작은 정리(Fermat's Little Theorem)