Fermat’s Little Theorem

2020-2학기, 대학에서 ‘현대대수1’ 수업을 듣고 공부한 바를 정리한 글입니다. 지적은 언제나 환영입니다 :)

---

우리는 $\mathbb{Z}_n$이 Ring임을 이미 알고 있다.

그런데, 이 $\mathbb{Z}_n$은 사실 아래의 Factor Ring으로부터 유도되는 Ring이다!

\[\mathbb{Z} / n \mathbb{Z} \cong \mathbb{Z}_n\]

그리고 우리는 $\mathbb{Z}_p$의 경우 Ring보다 상위 단계인 Field가 됨을 확인하였다!!

$\mathbb{Z}_p$에서 곱셈에 대한 군인 $\mathbb{Z}^{*}_p$를 생각해보자.

\[\mathbb{Z}^{*}_p = \{1, 2, ..., p-1 \}\]

즉, $\lvert \mathbb{Z}^{*}_p \rvert = p-1$이다.

이때, $a \in \mathbb{Z}^{*}_p$에 대해 $a$의 위수는 $\mathbb{Z}^{*}_p$의 위수의 약수이므로 $\lvert a \rvert \mid (p-1)$가 된다.

따라서 $a^{p-1} = 1$이 된다.

이것을 $\mathbb{Z}$에서 다시 쓰면 아래와 같다.

\[a^{p-1} \equiv 1 \quad (\textrm{mod} \; p)\]

이때, $a$를 $\mathbb{Z}^{*}_p$에서 뽑았으므로 $a \not\equiv 0$ (mod $p$)이다. 즉, $p \not\mid a$이다.

위의 사실을 잘 정리하여 기술한 것이 바로 Fermat’ Little Theorem이다.

---

Fermat’s Little Theorem

Theorem. Fermat’s Little Theorem

Let $p$ be a prime,

If $a \in \mathbb{Z}$, and $p \not\mid a$,

then $p \mid (a^{p-1} + 1)$ $\iff$ $a^{p-1} \equiv 1$ (mod $p$).

이때, 만약 $p \mid a$라면,
$a^{p-1} \equiv 0$ (mod $p$)가 된다!

Corollary.

If $a \in \mathbb{Z}$, then $a^p \equiv a$ (mod $p$).

proof.

(Case 1) $p \mid a$

(Case 2) $p \not\mid a$

Examples

Example 1.

$8^{103} \equiv \; ?$ (mod 13)

Sol.

By Fermat-, $8^{12} \equiv 1$ (mod 13)

$\implies$ $(8^{12})^{8} \cdot 8^7 \equiv 1 \cdot 8^7$ (mod 13)

$\implies$ $8^7 \equiv (-5)^7 \equiv (25)^3 \cdot (-5)$

이때, $25 \equiv -1$ (mod 13) 이므로

$\implies$ $(-1)^3 (-5) \equiv 5$ (mod 13)

Example 2.

$2^{11213} \equiv \; ?$ (mod 11)

Sol.

By Fermat-, $2^{10} \equiv 1$ (mod 11)

$(2^{10})^{1121} \cdot 2^3 \equiv 1 \cdot 8$ (mod 11)

---

Example 3.

Show that, for $\forall \; n \in \mathbb{N}$, $15 \mid (n^{33} - n)$.

Sol.

$15 \mid (n^{33} - n)$. 즉, $n^{33} - n = n(n^{32} - 1) \equiv 0$ (mod 15)임을 보이면 된다.

이때, $15 = 3 \times 5$이고, Fermat의 정리에 따르면

• for $3 \not\mid n$, $n^2 \equiv 1$ (mod 3)
• for $5 \not\mid n$, $n^4 \equiv 1$ (mod 5)

이제 $n^{32}$를 Fermat 정리를 이용해 표현하면 아래와 같다.

• if $3 \not\mid n$, $n^{32} \equiv (n^2)^{16} \equiv 1$ (mod 3)
• if $5 \not\mid n$, $n^{32} \equiv (n^4)^{8} \equiv 1$ (mod 5)

케이스를 나누어 $n^{32} - 1$을 분석해보자.

1. $3 \not\mid n$ and $5 \not\mid n$

then, $3 \mid (n^{32} - 1)$ and $5 \mid (n^{32}-1)$을 의미한다.

따라서 $15 \mid (n^{32} - 1)$을 얻는다.

따라서 $(n^{32} - 1) \equiv 0$ (mod 15)이다.

2. $3 \mid n$ and $5 \mid n$

이것은 $15 \mid n$를 의미하므로 $15 \mid n(n^{32}-1)$이다.

3. $3 \not\mid n$ and $5 \mid n$

$3 \mid (n^{32} - 1)$이므로 $3 \mid n(n^{32} - 1)$이다. 또한, $5 \mid n(n^{32} - 1)$이므로

$15 \mid n(n^{32}-1)$이다.

4. $3 \mid n$ and $5 \not\mid n$

3.의 경우와 마찬가지이다.

---

Fermat’s Little Theorem은 Ring의 Multiplicative group으로부터 쉽게 유도할 수 있는 성질이었다 ㅎㅎ

하.지.만.!

Euler 형님이 우리를 위해 FLT를 일반화 해주셨다 ㅠㅠ

Euler’s Theorem