Fermat Little Theorem

Fermat Little Theorem (FLT)

Pada kesempatan kali ini kita akan membahas tentang Fermat Little Theorem atau yang biasa dikenal dengan singkatan FLT. Teorema ini sendiri juga sering dijumpai pada soal-soal matematika khususnya pada bagian teori bilangan atau Number Theory

FLT. Diberikan bilangan bulat positif $a$ dan sebuah bilangan prima $p$ maka berlaku
$$a^p\equiv a \pmod p$$

Bukti. Kita akan membuktikan Fermat Little Theorem dengan induksi matematika. Untuk $a=1$ teorema benar, sekarang kita asumsikan untuk $a=k$ teorema benar. Maka kita harus membuktikan $(k+1)^p\equiv k+1 \pmod p$.
$$\begin{align*} (k+1)^p - (k+1)&\equiv (k^p-k) + \sum_{n=1}^{p-1} {p\choose n}k^n \pmod p \\ &\equiv k^p-k \pmod p \\ &\equiv 0 \pmod p\end{align*}$$
jadi teorema benar. Perlu diingat bahwa $p|{p\choose n}$ untuk setiap $1\le n $

Ada sebuah teorema yaitu Teorema Euler yang bisa dibilang mirip dengan Fermat Little Theorem tetapi berlaku untuk sebuah bilangan bulat $a$ dan $b$ dimana $b$ tidak harus prima namun $\gcd{(a,b)}=1$. Sebelum membahas tentang Teorema Euler kita harus mengetahui suatu fungsi yaitu euler phi function yang biasa dilambangkan dengan $\varphi(n)$. $\varphi(n)$ menyatakan banyaknya bilangan yang lebih kecil dari $n$ dan relatif prima dengan $n$, contohnya $\varphi(8)=4,\varphi(20)=8,$ dan lain lain.

Euler Theorem. Untuk sembarang bilangan bulat positif $a$ dan $n$ yang saling relatif prima, maka berlaku
$$a^{\varphi(n)}\equiv 1\pmod n$$

Bukti. Misalkan himpunan $S=\{s_1,s_2,\cdots,s_{\varphi(n)}\}$ dimana $s_i(i=1,2\cdots,\varphi(n))$ dan $a$ semuanya relatif prima dengan $n$. Perhatikan bilangan $s_1a,s_2a,\cdots,s_{\varphi(n)}a$ semuanya relatif prima dengan $n$. Misalkan $t_i$ adalah sisa dari $s_ia$ saat dibagi dengan $n$, hal ini berarti $t_i\in S$. Kita claim bahwa tidak ada bilangan bulat $i\not =j$ sedemikian hingga $t_i=t_j$, asumsikan ada maka $s_ia\equiv s_ja\pmod n\implies s_i\equiv s_j\pmod n$ dimana hal ini tidak mungkin. Jadi dapat disimpulkan bahwa $t_i$ merupakan permutasi dari $s_i$
$$\begin{align*} s_1a\cdot s_2a\cdot\cdots\cdot s_{\varphi(n)}a&\equiv s_1\cdot s_2\cdot\cdots\cdot s_{\varphi(n)} \pmod n \\ Ha^{\varphi(n)}&\equiv H\pmod n\\ a^{\varphi(n)}&\equiv 1 \pmod n\end{align*}$$
dimana $H=s_1\cdot s_2\cdot\cdots\cdot s_{\varphi(n)}$