Teorema Kecil Fermat

Teorema kecil Fermat merupakan salah satu teori penting yang mendasari berbagai macam teorema penting lain di dalam teori bilangan. Pada tulisan ini akan dijelaskan isi dan bukti dari teorema kecil Fermat beserta contoh pengaplikasiannya. Selain itu, salah satu perumuman dari teorema kecil Fermat juga akan dibahas.

Teorema 1 [Teorema Kecil Fermat]

[box] Jika $p$ bilangan prima, maka untuk setiap bilangan bulat positif $a$ berlaku $a^p\equiv a\pmod{p}$ . Lebih lanjut, jika $a$ dan $p$ saling relatif prima, maka berlaku $\displaystyle a^{p-1}\equiv 1{\pmod {p}}$ . [/box]

[learn_more caption=”Bukti:” state=”open”]

Cukup dibuktikan pernyataan kedua. Misalkan $a$ adalah bilangan bulat positif yang relatif prima dengan $p$ . Perhatikan bahwa bilangan

$a,2a,\ldots,(p-1)a$

masing-masing memiliki sisa yang berbeda dalam modulo $p$ . Akibatnya, diperoleh

$a(2a)\ldots((p-1)a)\equiv 1.2.\ldots (p-1)\pmod{p}\iff (p-1)!a^{p-1}\equiv (p-1)!\pmod{p}.$

Karena $FPB(p,(p-1)!)=1$ , diperoleh

$a^{p-1}\equiv 1\pmod{p}.$

[/learn_more]

Secara umum, teorema ini sering dimanfaatkan dalam mencari sisa pembagian suatu bilangan oleh suatu bilangan prima.

Contoh:

Tentukan sisa pembagian $2^{2020}$ oleh 13.

Solusi:

Perhatikan bahwa 13 merupakan bilangan prima dan $2020=168\times 12+4$ . Diperoleh

$\begin{eqnarray*} 2^{2020}&\equiv& 2^{168\times 12+4}\pmod{13}\equiv \left(2^{12}\right)^{168}2^4\pmod{13}\\ &\equiv& 1^{168}2^{4}\pmod{13}\equiv 16\pmod{13}\\ &\equiv& 3\pmod{13}. \end{eqnarray*}$

Dengan demikian, sisa pembagiannya adalah $3$ .

Contoh:

Diberikan bilangan prima $p\geq7$ . Tunjukkan bahwa

$\underbrace{11\ldots1}_{(p-1)\ \text{kali}}$

habis dibagi oleh $p$ .

Solusi:

Diperhatikan bahwa

$\underbrace{11\ldots1}_{(p-1)\ \text{kali}}=\frac{10^{p-1}-1}{9}.$

Karena $10$ dan $p$ saling relatif prima, berdasarkan Teorema Kecil Fermat diperoleh $p$ habis membagi $10^{p-1}-1$ . Akibatnya,

$\underbrace{11\ldots1}_{(p-1)\ \text{kali}}$

habis dibagi oleh $p$ .

Generalisasi: Teorema Euler

Terdapat berbagai macam perumuman dari teorema kecil Fermat, salah satunya dalah Teorema Euler. Sebelum membahas teorema tersebut, akan dibahas mengenai fungsi Euler terlebih dahulu. Fungsi Euler adalah fungsi $\varphi:\mathbb{N}\to\mathbb{N}$ definisikan sebagai berikut: untuk setiap bilangan bulat positif $n$ , $\varphi(n)$ adalah banyaknya bilangan bulat positif $n$ dan relatif prima dengan $n$ . Beberapa sifat dasar dari fungsi Euler diberikan dalam proposisi berikut.

Proposisi 1

[box]

$\varphi(1)=1$ .
$n$ merupakan bilangan prima jika dan hanya jika $\varphi(n)=p-1$
Jika $n=p^a$ dengan $p$ merupakan bilangan prima dan $a$ bilangan bulat positif, maka $\varphi(n)=p^a-p^{a-1}$ .[/box]

Selanjutnya akan diberikan formula untuk menghitung $\varphi(n)$ untuk setiap bilangan bulat positif $n$ .

Definisi:

Jelas bahwa untuk setiap $m$ , himpunan semua bilangan bulat positif yang kurang dari $m$ dan relatif prima dengan $m$ adalah himpunan kelas residu tereduksi lengkap modulo $m$ . Lebih lanjut, suatu himpunan kelas residu tereduksi lengkap modulo $m$ memiliki sebanyak $\varphi(m)$ anggota.

Proposisi 2

[box] Jika $a$ dan $b$ bilangan bulat positif yang relatif prima, maka $\varphi(ab)=\varphi(a)\varphi(b)$ . [/box]

[learn_more caption=”Bukti:” state=”open”]

Disusun bilangan $1,2,\ldots,ab$ sebagai berikut:

$\begin{array}{cccc} 1&2&\ldots&a\\ a+1&a+2&\ldots&2a\\ \vdots&\vdots&\vdots&\vdots\\ a(b-1)+1&a(b-1)+2&\ldots&ab. \end{array}$

Jelas bahwa di antara bilangan-bilangan $1,2,\ldots,ab$ terdapat $\varphi(ab)$ bilangan yang relatif prima dengan $ab$ . Di lain pihak, terdapat $\varphi(a)$ kolom yang mengandung bilangan-bilangan yang relatif prima dengan $a$ . Karena setiap kolom merupakan himpunan kelas residu lengkap modulo $b$ , maka terdapat tepat $\varphi(b)$ bilangan pada masing-masing kolom yang relatif prima dengan $b$ . Akibatnya, banyaknya bilangan yang relatif prima dengan $ab$ pada susunan tersebut adalah $\varphi(a)\varphi(b)$ . Jadi, $\varphi(ab)=\varphi(a)\varphi(b)$ .

[/learn_more]

Dengan mengkombinasikan Proposisi 1 dan Proposisi 2, diperoleh formula umum dari fungsi Euler sebagai berikut.

Teorema

[box] Diberikan bilangan bulat positif $n$ . Jika $n=p_1^{\alpha_1}p_2^{\alpha_2}\ldots p_k^{\alpha_k}$ faktorisasi prima dari $n$ , maka

$\varphi(n)=n\left(1-\frac{1}{p_1}\right)\left(1-\frac{1}{p_2}\right)\ldots \left(1-\frac{1}{p_k}\right).$

[/box]

Contoh:

Tunjukkan bahwa ada tak hingga banyaknya bilangan bulat positif $n$ dengan sifat $\varphi(n)$ merupakan kelipatan 10.

Solusi:

Diambil $n=11^k,\ k=1,2,\ldots$ . Diperoleh $\varphi(11^k)=11^k-11^{k-1}=10.11^{k-1}$ yang merupakan kelipatan 10.

Teorema Euler diberikan dalam teorema berikut.

Teorema 2

[box] Jika $a$ dan $m$ bilangan bulat positif dengan $FPB(a,m)=1$ , maka $a^{\varphi(m)}\equiv1\pmod{m}$ .[box]

[learn_more caption=”Bukti:” state=”open”]

Misalkan $S=\{a_1,a_2,\ldots,a_{\varphi(m)}\}$ himpunan semua bilangan bulat positif yang kurang dari $m$ dan relatif prima dengan $m$ . Jelas bahwa $S$ merupakan himpunan kelas residu tereduksi lengkap modulo $m$ . Karena $FPB(a,m)=1$ , diperoleh

$\{aa_1,aa_2,\ldots,aa_{\varphi(m)}\}$

juga merupakan himpunan kelas residu tereduksi lengkap modulo $m$ . Akibatnya diperoleh

$(aa_1)(aa_2)\ldots(aa_{\varphi(m)})\equiv a_1a_2\ldots a_{\varphi(m)}\pmod{m}.$

Karena $FPB(a_k,m)=1,\ k=1,2,\ldots,\varphi(m)$ , diperoleh

$a^{\varphi(m)}\equiv 1\pmod{m}.$

[/learn_more]

Contoh:

Tentukan sisa pembagian $2^{2020}$ oleh 49.

Solusi:

Perhatikan bahwa $\varphi{49}=42$ . Berdasarkan Teorema Euler, diperoleh

$\begin{eqnarray*} 2^{2020}&\equiv& 2^{13+7}\pmod{13}\equiv 2^{13}.2^7\pmod{13}\\ &\equiv& 2^{8}\pmod{13}\equiv 256\pmod{13}\\ &\equiv& 9\pmod{13}. \end{eqnarray*}$

Dengan demikian, sisa pembagiannya adalah $13$ .

Contoh:

Diberikan bilangan prima $p>5$ . Tunjukkan bahwa $p^8\equiv1\pmod{240}$ .

Solusi:

Diperhatikan bahwa $240=2^4.3.5$ . Berdasarkan Teorema Kecil Fermat, $p^2\equiv1\pmod{3}$ dan $p^4\equiv1\pmod{5}$ . Karena $\gcd(p,2^4)=1$ dan $\varphi(2^4)=8$ , maka berdasarkan Teorema Euler diperoleh $p^8\equiv1\pmod{16}$ . Jadi, $p^8\equiv1\pmod{m}$ untuk $m=3,5$ dan $16$ . Akibatnya $p^8\equiv1\pmod{240}$ .

Selanjutnya, Pembaca dapat mengerjakan soal-soal berikut sebagai latihan.

Tentukan sisa pembagian $2^{2020}$ oleh $2019$ .
Tentukan sisa pembagian $2^{2019}$ oleh $2020$ .
Tunjukkan bahwa untuk setiap bilangan bulat positif $n$ berlaku $n^9\equiv n^3\pmod{504}$ .
Diberikan $p$ dan $q$ bilangan prima berbeda. Tunjukkan bahwa berlaku
$pq|(20^{pq}-20^p-20^q+20).$
Tunjukkan bahwa untuk setiap bilangan genap positif $n$ berlaku $n^2|2^{n!}-1$ .
Tunjukkan bahwa untuk setiap bilangan prima $p>5$ berlaku $p^4-1$ merupakan kelipatan $240$ .
a. Tentukan jumlah semua bilangan bulat positif yang kurang dari $2020$ dan relatif prima dengan 2020.
b. Tentukan jumlah semua bilangan bulat positif yang kurang dari $4040$ dan relatif prima dengan 2020.
Diberikan $p$ bilangan prima. Tunjukkan bahwa $p$ membagi $ab^p-ba^p$ untuk setiap bilangan bulat positif $a$ dan $b$ .

Teorema Kecil Fermat

Published by made.tantrawan on October 21, 2020October 21, 2020

Teorema Kecil Fermat

Generalisasi: Teorema Euler

0 Comments

Leave a Reply Cancel reply

Relasi Urutan Pada Bilangan Bulat

Sistem Bilangan Bulat

Operasi Perkalian Pada Sistem Bilangan Asli

Teorema Kecil Fermat

Published by made.tantrawan on October 21, 2020October 21, 2020

Teorema Kecil Fermat

Generalisasi: Teorema Euler

0 Comments

Leave a Reply Cancel reply

Related Posts

Relasi Urutan Pada Bilangan Bulat

Sistem Bilangan Bulat

Operasi Perkalian Pada Sistem Bilangan Asli