02. 페르마의 소정리(Fermat's little theorem)

● 정의
- p가 소수일 때 p와 서로소인 a에 대해서 a^(p-1)≡1(mod p)가 성립한다.
- a^(p-1)≡1(mod p) → a^(p)≡a(mod p) 합동(Congruence)참조

● 증명
① A={1,2,3,4,5......(p-1)} 집합A를 정의한다.
② p가 소수이기 때문에, 집합A의 원소를 각각 p로 나눈 나머지는 모두 다르다.
③ B={1*a, 2*a, 3*a, 4*a, 5*a.......(p-1)*a} 집합B를 정의한다.
④ 집합B의 원소를 각각 p로 나눈 나머지는 모두 다르다.
※ 증명
ⓐ B의 원소 중 2개를 선택한다. (각각 a*m, a*n으로 정의한다. m≠n )
ⓑ a*m과 a*n을 p로 나눈 나머지가 같다고 가정한다. a*m≡a*n(mod p) → 가정이 맞지 않는다는 것을 증명하기 위해서
ⓒ a*m≡a*n(mod p) → (a*m) - (a*n)≡0(mod p)
Ⅰ. 합동(Congruence)에서 a≡b(mod p), c≡d(mod p)일 때, a+c≡b+d(mod p)라는 것을 증명했다.
Ⅱ. a*m≡r(mod p), a*n≡r(mod p) (ⓑ가정에 의해서 나머지가 r로 같다. )
Ⅲ. a*m+ -(a*n)≡r+ -(r)(mod p)
ⅳ. 즉, (a*m)-(a*n)≡0(mod p)가 성립한다.
ⓓ a(m*n)≡0(mod p)
ⓔ p는 a(m*n)의 배수라는 결과가 나온다. 따라서 p가 소수라는 전제에 위된다.
∵ a*m과 a*n을 p로 나눈 나머지는 같지 않다. 즉 집합B의 원소를 각각 p로 나눈 나머지는 모두 다르다.
⑤ 집합A의 원소를 p로 나눈 나머지와 집합B의 원소를 p로 나눈 나머지는 같다.
⑥ 따라서 집합A의 원소를 모두 곱한 값의 나머지와 집합B의 원소를 모두 곱한 값의 나머지는 같다.
⑦ (p-1)!≡(p-1)!*a^(p-1)(mod p)
∵ a^(p-1)≡1(mod p)

● 예제
Q. 10^(6015)+10^(1203)-10^(15)-10^(k)가 2005의 배수가 될 때, k의 최소값은? (KMO)

A. k = 3

2005의 배수가 된다는 말은 401의 배수가 된다는 말로 바꿀 수 있다. ( 2005 = 15 * 401 )
6015=401*15, 1203=401*3
10^(401)≡10(mod 401)
10^(401*15))≡10^(15)(mod 401)
10^(401*3))≡10^(3)(mod 401)
∵ 10^(6015)+10^(1203)-10^(15)-10^(k) => 10^(3) - 10^(k)≡0(mod 401)