페르마의 소정리(Fermat's Little Theorem)

페르마의 소정리(Fermat's Little Theorem)는 정수론에서 매우 중요한 정리로, 다음과 같은 내용을 담고 있습니다.

📌 페르마의 소정리(Fermat's Little Theorem)

정리:
만약 ppp가 소수이고, aaa가 ppp로 나누어지지 않는 정수라면,

a^{p-1} \equiv 1 \pmod{p}
]

즉, ppp는 소수이고 gcd⁡(a,p)=1\gcd(a, p) = 1gcd(a,p)=1일 때,

ap−1mod  p=1a^{p-1} \mod p = 1ap−1modp=1

이 됩니다.

 

 

페르마의 소정리 증명 (모듈러 산술 기반)

여기서는 가장 기본적인 곱셈군의 성질과 모듈러 연산의 성질을 이용해 증명합니다.

🎯 전제 조건

• ppp는 소수
• aaa는 ppp의 배수가 아님, 즉 gcd⁡(a,p)=1\gcd(a, p) = 1gcd(a,p)=1

🔢 증명

1단계: 곱셈 집합을 구성

{1,2,3,...,p−1}\{1, 2, 3, ..., p-1\}{1,2,3,...,p−1} 은 모두 ppp보다 작은 양의 정수이자 ppp와 서로소입니다.

이 집합의 원소 각각에 aaa를 곱한 집합을 생각해 봅시다:

S={a⋅1,a⋅2,a⋅3,...,a⋅(p−1)}S = \{a \cdot 1, a \cdot 2, a \cdot 3, ..., a \cdot (p-1)\}S={a⋅1,a⋅2,a⋅3,...,a⋅(p−1)}

이제 이 집합을 모듈러 ppp 연산으로 바꾸면:

S′={a⋅1mod  p,a⋅2mod  p,...,a⋅(p−1)mod  p}S' = \{a \cdot 1 \mod p, a \cdot 2 \mod p, ..., a \cdot (p-1) \mod p\}S′={a⋅1modp,a⋅2modp,...,a⋅(p−1)modp}

2단계: 집합 SSS는 {1,2,...,p−1}\{1, 2, ..., p-1\}{1,2,...,p−1}와 동치

이 곱셈은 모듈러 ppp 위에서 일대일 대응을 이루며, 순열이 됩니다.

즉, a⋅i≡a⋅j(modp)a \cdot i \equiv a \cdot j \pmod{p}a⋅i≡a⋅j(modp) 이면
양변에 a−1a^{-1}a−1을 곱해 i≡j(modp)i \equiv j \pmod{p}i≡j(modp) 가 됩니다.
이는 i=ji = ji=j이므로 서로 다른 수가 충돌하지 않습니다.

따라서 곱한 집합 SSS는 원래 집합 {1,2,...,p−1}\{1,2,...,p-1\}{1,2,...,p−1}를 순서를 바꿔놓은 것과 같습니다.

---

3단계: 두 집합의 곱을 비교

양쪽 모두 곱을 취하면:

• 원래 집합 곱:1⋅2⋅...⋅(p−1)≡(p−1)!(modp)1 \cdot 2 \cdot ... \cdot (p-1) \equiv (p-1)! \pmod{p}1⋅2⋅...⋅(p−1)≡(p−1)!(modp)
• 곱셈한 집합:(a⋅1)(a⋅2)...(a⋅(p−1))=ap−1⋅(p−1)!(a \cdot 1)(a \cdot 2)...(a \cdot (p-1)) = a^{p-1} \cdot (p-1)!(a⋅1)(a⋅2)...(a⋅(p−1))=ap−1⋅(p−1)!

따라서 모듈러 ppp에서 같으므로:

ap−1⋅(p−1)!≡(p−1)!(modp)a^{p-1} \cdot (p-1)! \equiv (p-1)! \pmod{p}ap−1⋅(p−1)!≡(p−1)!(modp)

4단계: 약분

• ppp는 소수이므로 (p−1)!(p-1)!(p−1)!은 ppp와 서로소입니다.
• 따라서 모듈러 연산에서 (p−1)!(p-1)!(p−1)!로 약분 가능:

ap−1≡1(modp)a^{p-1} \equiv 1 \pmod{p}ap−1≡1(modp)

---

✅ 결론

ppp가 소수이고 aaa가 ppp로 나누어떨어지지 않을 때,

ap−1≡1(modp)a^{p-1} \equiv 1 \pmod{p}ap−1≡1(modp)

이로써 페르마의 소정리가 증명됩니다.