Teorema Wilson

Posting Komentar

Halo semuanya pada kesempatan kali ini admin akan membahas suatu topik dalam teori bilangan khususnya dalam modulo yakni tentang teorema wilson. Teorema ini cukup menarik karena melibatkan bilangan prima dan faktorial.

Buat kalian yang belum tau bilangan prima itu apa. Anda bisa berkunjung ke postingan saya tentang konsep bilangan prima. Oke langsung saja ke pembahasannya.

sumber : wikidata

Teorema Wilson :

Jika $p$ bilangan prima, maka $(p-1)!\equiv -1 \text{ mod } p$

Untuk membuktikan teorema wilson tersebut perhatikan lemma berikut terlebih dahulu.

Lemma :

Misalkan $a$ bilangan bulat dan $p$ prima. Jika $a^2\equiv 1 \text{ mod } p$ maka $a\equiv 1 \text{ mod } p$ atau $a\equiv -1 \text{ mod } p$

Bukti Lemma :

Misalkan $a^2\equiv 1 \text{ mod } p$ . Menurut definisi modulo kita punya $p|a^2-1$ . Ini sama halnya $p|(a-1)(a+1)$ . Karena $p$ prima maka haruslah $p|a-1$ atau $p|a+1$ . Dengan kata lain $a\equiv 1 \text{ mod } p$ atau $a\equiv -1 \text{ mod } p$

Bukti Teorema Wilson :

Perhatikan bahwa $(p-1)!=(p-1)(p-2)\cdots 2.1$ . Dengan demikian kita punya $(p-1)!\equiv (p-1)(p-2)\cdots 2.1 \text{ mod } p$ . Karena untuk setiap elemen dari $p-2, p-1,\cdots ,3,2$ terdapat tepat satu invers yang tidak sama dengan dirinya sendiri maka kita dapatkan $(p-2)(p-1)\cdots 3.2\equiv 1 \text{ mod } p$ . Sehingga kita punya $\begin{align*}(p-1)!&\equiv (p-1)(p-2)\cdots 2.1 \text{ mod } p\\ &\equiv (p-1).1.1 \text{ mod } p\\ &\equiv p-1 \text{ mod } p\\ &\equiv -1 \text{ mod } p\end{align*}$

Contoh : Kita tahu bahwa $7$ merupakan bilangan prima. Maka menurut teorema wilson $6!\equiv -1 \text{ mod } 7$ . Hal ini mudah ditunjukkan karena $6!=720\equiv 20\equiv 6 \equiv -1\text{ mod } 7$ .

Contoh Soal :

1. Tentukan sisa pembagian $28!$ jika dibagi $31$ .

2. Buktikan bahwa $437$ habis membagi $18!+1$ .

Baca Juga

3. Tentukan sisa pembagian dari $2016!-2015!$ oleh $2017$

Berikut adalah pembahasan dari soal tersebut :

1. Karena $31$ bilangan prima, maka menurut teorema wilson berlaku $30!\equiv -1 \text{ mod } 31$ . Misalkan $x=28!$ , kita punya $30!=30\times 29\times 28!=870x$ . Sehingga kita dapatkan $\begin{align*} 30! &\equiv -1 \text{ mod } 31\\ 870x &\equiv 30 \text{ mod } 31\\ 29x &\equiv 1 \text{ mod } 31\\ 29x &\equiv 1+31\times 14 \text{ mod } 31\\ 29x &\equiv 435 \text{ mod } 31\\ x &\equiv 15 \text{ mod } 31\end{align*}$ .

Jadi, $28!$ dibagi $31$ bersisa 15.

2. Perhatikan bahwa $437=19\times 23$ . Karena $19$ prima maka menurut teorema wilson $18!\equiv -1 \text{ mod } 19$ . Dengan kata lain, $19$ habis membagi $18!+1$ . Oleh karena itu, akan ditunjukan bahwa $23$ habis membagi $18!+1$ . Karena $23$ prima maka menurut teorema wilson $22!\equiv -1 \text{ mod } 23$ . Misalkan $x=18!$ , kita punya

$\begin{align*}22!&=22\times 21\times 20\times 19\times 18!\\ &=22\times 21\times 20\times 19x\end{align*}$ . Sehingga kita dapatkan $\begin{align*} 22! &\equiv -1 \text{ mod } 23\\ 22\times 21\times 20\times 19x &\equiv 22 \text{ mod } 23\\ 21\times 20\times 19x &\equiv 1 \text{ mod } 23\\ 21\times 20\times 19x &\equiv 24 \text{ mod } 23\\ 7\times 5\times 19x &\equiv 2 \text{ mod } 23\\ 7\times 5\times 19x &\equiv 25 \text{ mod } 23\\ 7\times 19x &\equiv 5 \text{ mod } 23\\ 7\times 19x &\equiv 28 \text{ mod } 23\\ 19x &\equiv 4 \text{ mod } 23\\ 19x &\equiv -19 \text{ mod } 23\\ x &\equiv -1 \text{ mod } 23\end{align*}$

Persamaan terakhir memberikan bahwa $18!$ bersisa $-1$ jika dibagi oleh $23$ . Dan kita selesai membuktikan pernyataan pada soal.

3. Perhatikan bahwa

$\begin{align*}2015!&\equiv 2016!.2016^{-1} \text{ mod } 2017\\ &\equiv (-1).2016 \text{ mod } 2017\\ &\equiv (-1).(-1) \text{ mod } 2017\\ &\equiv 1\text{ mod } 2017\end{align*}$