Movatterモバイル変換

Teorema Wilson

Dari Wikipedia bahasa Indonesia, ensiklopedia bebas

Dalamteori bilangan,Teorema Wilson menyatakan bahwa bilangan bulatn > 1 adalahbilangan prima jika dan hanya jika perkalian semuabilangan bulat positif yang lebih kecil darin mempunyai selisih 1 dengan suatu kelipatan darin. Dengan menggunakanfaktorial $(n-1)!=1\times 2\times 3\times \cdots \times (n-1)$ dan menggunakan notasiaritmetika modular, teorema ini dapat dituliskan sebagai

$(n-1)!\ \equiv \;-1{\pmod {n}}$

benar jika dan hanya jikan adalah bilangan prima. Dengan bahasa lain,n adalah bilangan prima jika dan hanya jika (n − 1)! + 1 habis dibagi olehn.^[1]

Sejarah

[sunting |sunting sumber]

Teorema ini dinyatakan olehIbnu Haitham (sekitar 1000 M),^[2] dan pada abad ke-19 olehJohn Wilson.^[3]Edward Waring mengumumkan teorema tersebut pada tahun 1770, walau dia maupun muridnya, Wilson, dapat membuktikannya.Langrage memberikan bukti pertama pada tahun 1771.^[4] Terdapat bukti bahwaLeibniz juga menyadari bukti teorema tersebut satu abad sebelumnya, tetapi ia tidak pernah mempublikasikannya.^[5]^[6]

Contoh

[sunting |sunting sumber]

Untuk bilangann dari 2 sampai 30, tabel berikut berisi bilangan (n − 1)! dan sisa pembagiannya dengann. Warna latar biru digunakan untukn termasukbilangan prima, dan emas untukbilangan komposit.

Tabel faktorial dan sisa pembagiannya dengan $n {\displaystyle n}$
$n {\displaystyle n}$	$(n-1)!$ (barisanA000142 padaOEIS)	$(n-1)!\ {\bmod {\ }}n$ (barisanA061006 padaOEIS)
2	1	1
3	2	2
4	6	2
5	24	4
6	120	0
7	720	6
8	5040	0
9	40320	0
10	362880	0
11	3628800	10
12	39916800	0
13	479001600	12
14	6227020800	0
15	87178291200	0
16	1307674368000	0
17	20922789888000	16
18	355687428096000	0
19	6402373705728000	18
20	121645100408832000	0
21	2432902008176640000	0
22	51090942171709440000	0
23	1124000727777607680000	22
24	25852016738884976640000	0
25	620448401733239439360000	0
26	15511210043330985984000000	0
27	403291461126605635584000000	0
28	10888869450418352160768000000	0
29	304888344611713860501504000000	28
30	8841761993739701954543616000000	0

Bukti

[sunting |sunting sumber]

Semua pembuktian berikut menggunakan fakta bahwa kelas residu modulo bilangan prima adalah suatulapangan—lihat artikellapangan prima untuk detailnya.Teorema Lagrange yang menyatakan bahwa setiap lapanganpolinomial berderajatn memiliki maksimaln akar, digunakan dalam semua pembuktian.

Modulus komposit

[sunting |sunting sumber]

Jika $n {\displaystyle n}$ adalah bilangan komposit, maka ia dapat dibagi dengan suatu bilangan prima $q {\displaystyle q}$ yang terletak diantara $2\leq q\leq n-2$ . Karena $q {\displaystyle q}$ membagi $n {\displaystyle n}$ , misalkan $n=qk$ untuk suatu bilangan bulat $k {\displaystyle k}$ . Dengan menggunakankontradiksi, anggaplah $(n-1)!\equiv -1\,({\text{mod}}\,n)$ untuk $n {\displaystyle n}$ komposit. Karena $q {\displaystyle q}$ adalah faktor dari $n {\displaystyle n}$ , maka berlaku $(n-1)!\equiv -1\,({\text{mod}}\,q)$ . Namun $q {\displaystyle q}$ juga faktor dari $(n-1)!$ , sehingga juga berlaku $(n-1)!\equiv 0\,({\text{mod}}\,q)$ . Terjadi kontradiksi, dan dapat disimpulkan $(n-1)!\equiv -1\,({\text{mod}}\,n)$ hanya terjadi jika $n {\displaystyle n}$ bilangan prima.

Aplikasi

[sunting |sunting sumber]

Uji keprimaan

[sunting |sunting sumber]

Walaupun dapat digunakan sebagai salah satuuji keprimaan, pada praktiknya teorema Wilson tidak pernah dipakai. Hal disebabkan karena menghitung nilai (n − 1)! modulon untuk bilangann yang besar secara komputasional berat, dan karena ada banyak uji keprimaan yang lebih cepat.

Residu kuadratik

Artikel utama:residu kuadratik

Dengan menggunakan teorema Wilson, kita dapat mengubah ruas kiri setiap bilangan prima ganjil $p=2m+1$ di

1\cdot 2\cdots (p-1)\ \equiv \ -1\ {\pmod {p}}

untuk mendapatkan persamaan $1\cdot (p-1)\cdot 2\cdot (p-2)\cdots m\cdot (p-m)\ \equiv \ 1\cdot (-1)\cdot 2\cdot (-2)\cdots m\cdot (-m)\ \equiv \ -1{\pmod {p}}.$ Bentuk tersebut dapat dinyatakan sebagai

\prod _{j=1}^{m}\ j^{2}\ \equiv (-1)^{m+1}{\pmod {p}}

atau

(m!)^{2}\equiv (-1)^{m+1}{\pmod {p}}.

Bentuk ini dapat digunakan untuk membuktikanteorema terkenal: untuk setiap bilangan prima $p {\displaystyle p}$ yang memenuhi $p\equiv 1\,({\text{mod}}\,4)$ , bilangan $-1$ adalah residu kuadratik modulo $p {\displaystyle p}$ . Untuk membuktikannya, anggap $p=4k+1$ untuk suatu nilai $k {\displaystyle k}$ . Dengan mengambil $m=2k$ dan menggunakan bentuk diatas, kita dapatkan $-1$ kongruen dengan $(m!)^{2}$ .

Persamaan untuk bilangan prima

[sunting |sunting sumber]

Teorema Wilson telah digunakan untuk mengonstruksi persamaan bilangan prima, namun metode tersebut terlalu lambat untuk kegunaan praktis.

Fungsi gamma p-adic

[sunting |sunting sumber]

Teorema Wilson dapat digunakan untuk mendefinisikanfungsi gamma p-adic.

Generalisasi Gauss

[sunting |sunting sumber]

Gauss membuktikan bahwa^[7]

\prod _{k=1 \atop \gcd(k,m)=1}^{m}\!\!k\ \equiv {\begin{cases}-1{\pmod {m}}&{\text{if }}m=4,\;p^{\alpha },\;2p^{\alpha }\\\;\;\,1{\pmod {m}}&{\text{otherwise}}\end{cases}}

dengan $p {\displaystyle p}$ menyatakan bilangan prima ganjil, dan $\alpha$ menyatakan bilangan bulat positif. Nilai $m {\displaystyle m}$ yang menyebabkan hasil perkalian $-1$ adalah bilangan yang memiliki akar primitif modulom.

Hal ini memperumum faktr bahwa untuk setiapgrup abelianfinite, antara hasil perkalian semua elemennya adalahelemen identitas, atau terdapat tepat satu elemen $a {\displaystyle a}$ berorde dua (namun tidak keduanya). Pada kasus yang kedua, hasil perkalian semua elemen adalah elemen $a {\displaystyle a}$ .

Referensi

[sunting |sunting sumber]

^Darling, David.The Universal Book of Mathematics. hlm. 350. Parameter|url-status= yang tidak diketahui akan diabaikan (bantuan)
^"Ibn al-Haytham - Biography".Maths History (dalam bahasa Inggris). Diakses tanggal2021-02-10.
^Waring, Edward (1770).Meditationes Algebraicae (dalam bahasa Latin). Cambridge, England. hlm. 218. Parameter|url-status= yang tidak diketahui akan diabaikan (bantuan)
^Nouveaux mémoires de l'Académie royale des sciences et belles-lettres: avec l'histoire pour la même année (dalam bahasa Prancis). Chrétien Fréderic Voss. 1773.
^Bollettino di bibliografia e storia delle scienze matematiche ... (dalam bahasa Italia). C. Clausen. 1899.
^Giuseppe Peano (1897).Formulaire de mathématiques: t. I-V (dalam bahasa French). Harvard University. Bocca frères, Ch. Clausen. Pemeliharaan CS1: Bahasa yang tidak diketahui (link)
^Gauss, DA, art. 78

Diperoleh dari "https://id.wikipedia.org/w/index.php?title=Teorema_Wilson&oldid=23984777"

Kategori tersembunyi:

[8]ページ先頭