Fermat’s Little Theorem

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

December 26, 2020 4 minute read

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

우리는 $Z_{n}$ 이 Ring임을 이미 알고 있다.

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

Z / n Z ≅ Z_{n}

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

$Z_{p}$ 에서 곱셈에 대한 군인 $Z_{p}^{*}$ 를 생각해보자.

Z_{p}^{*} = {1, 2, . . ., p - 1}

즉, $| Z_{p}^{*} | = p - 1$ 이다.

이때, $a \in Z_{p}^{*}$ 에 대해 $a$ 의 위수는 $Z_{p}^{*}$ 의 위수의 약수이므로 $| a | ∣ (p - 1)$ 가 된다.

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

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

a^{p - 1} \equiv 1 (mod p)

이때, $a$ 를 $Z_{p}^{*}$ 에서 뽑았으므로 $a ≢ 0$ (mod $p$ )이다. 즉, $p ∤ a$ 이다.

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

Fermat’s Little TheoremPermalink

Theorem. Fermat’s Little Theorem

Let $p$ be a prime,

If $a \in Z$ , and $p ∤ a$ ,

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

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

Corollary.

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

proof.

(Case 1) $p ∣ a$

(Case 2) $p ∤ a$

ExamplesPermalink

Example 1.

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

Sol.

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

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

$⟹$ $8^{7} \equiv (- 5)^{7} \equiv (25)^{3} \cdot (- 5)$

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

$⟹$ $(- 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 N$ , $15 ∣ (n^{33} - n)$ .

Sol.

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

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

for $3 ∤ n$ , $n^{2} \equiv 1$ (mod 3)
for $5 ∤ n$ , $n^{4} \equiv 1$ (mod 5)

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

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

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

1. $3 ∤ n$ and $5 ∤ n$

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

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

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

2. $3 ∣ n$ and $5 ∣ n$

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

3. $3 ∤ n$ and $5 ∣ n$

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

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

4. $3 ∣ n$ and $5 ∤ n$

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

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

하.지.만.!

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

Euler’s Theorem

Seokyun Ha (aka. bluehorn07)

Fermat’s Little Theorem

Fermat’s Little TheoremPermalink

ExamplesPermalink

You may also enjoy

Hermite Interpolation

Interpolation for Uniformly Spaced Nodes, Runge Phenomenon

Interpolation Error

Newton’s Divided Differences