Teorema Wilson

Dalam aljabar dan teori bilangan, teorema Wilson menyatakan bahwa bilangan asli $n>1$ merupakan bilangan prima jika dan hanya jika darab dari semua bilangan asli yang kurang dari $n$ bernilai satu kurangnya dari suatu kelipatan $n$ . Dengan menggunakan notasi aritmetika modular, maka faktorial $(n-1)!=1\times 2\times 3\times \cdots \times (n-1)$ akan memenuhi relasi kekongruenan

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

ketika $n$ merupakan bilangan prima. Dengan kata lain, $n$ merupakan bilangan prima jika dan hanya jika $(n-1)!+1$ habis dibagi oleh $n$ .^[1]

Sejarah

Teorema ini dinyatakan oleh Ibnu al-Haitsam ca 1000 M.^[2] Edward Waring mengumumkan teorema tersebut pada tahun 1770 tanpa membuktikannya. Ia mengatributkan muridnya, John Wilson, atas penemuan tersebut.^[3] Langrage memberikan bukti pertama pada tahun 1771.^[4] Terdapat bukti bahwa Leibniz juga menyadari kebenaran teorema tersebut satu abad sebelumnya, tetapi ia tidak pernah menerbitkannya.^[5]^[6]

Contoh

Untuk setiap nilai $n$ dari 2 sampai 30, tabel berikut berisi bilangan $(n-1)!$ beserta sisa pembagian saat $(n-1)!$ dibagi oleh $n$ . Dalam aritmetika modular, sisa dari $a$ ketika dibagi oleh $n$ dinotasikan sebagai $a{\bmod {n}}$ . Warna latar biru digunakan untuk $n$ yang bernilai prima, dan kuning untuk $n$ yang bernilai komposit.

Tabel faktorial serta sisa pembagiannya oleh $n$
$n$	$(n-1)!$ (barisan A000142 pada OEIS)	$(n-1)!\ {\bmod {\ }}n$ (barisan A061006 pada OEIS)
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

Sebagai pernyataan bikondisional (jika dan hanya jika), maka pembuktiannya memiliki dua bagian: tunjukkan bahwa kekongruenannya tidak akan berlaku ketika $n$ merupakan bilangan komposit, dan tunjukkan bahwa kekongruenannya pasti berlaku saat $n$ merupakan bilangan prima.

Modulus komposit

Misalkan $n$ adalah bilangan komposit, maka ia habis dibagi oleh suatu bilangan prima $p$ , dengan $2\leq p<n$ . Oleh karena $p$ habis membagi $n$ , maka terdapat suatu $k\in \mathbb {Z}$ sedemikian sehingga $n=pk$ . Misalkan—dengan dalih untuk mencari kontradiksi—nilai $(n-1)!$ kongruen dengan $-1$ dalam modulo $n$ . Perhatikan bahwa $(n-1)!+1=nN=(pk)N=p(kN)$ untuk suatu $N\in \mathbb {N}$ . Akibatnya, $(n-1)!$ kongruen dengan $-1$ dalam modulo $p$ .

Di sisi lain, dari informasi $2\leq p\leq n-1$ , maka salah satu faktor dari darab $(n-1)!=(n-1)\times (n-2)\times \ldots \times 3\times 2\times 1$ ialah $p$ , sehingga $(n-1)!\equiv 0{\pmod {p}}$ . Oleh karena terjadi kontradiksi, maka asumsi di awal—bahwa nilai $(n-1)!$ kongruen dengan $-1$ dalam modulo $n$ —tidak mungkin terjadi jika $n$ komposit.

Lebih lanjut, jika $n$ merupakan bilangan komposit, maka $(n-1)!$ akan kongruen dengan 0 dalam modulo $n$ , kecuali untuk kasus $n=4$ , yaitu $3!\equiv 2{\pmod {4}}$ . Bukti dari pernyataan tersebut dapat dibagi menjadi dua kasus:

Jika $n$ merupakan kuadrat dari suatu bilangan prima $q>2$ , maka ${\begin{aligned}2&<q\\2q&<q^{2}=n\\2q&<n\\2<q<2q&<n\end{aligned}}$ Akibatnya, $q$ dan $2q$ akan muncul sebagai faktor dari $(n-1)!=(n-1)\times (n-2)\times \ldots \times 3\times 2\times 1$ , sehingga $(n-1)!$ habis dibagi oleh $q^{2}$ .
Jika $n$ bukan merupakan kuadrat dari suatu bilangan prima, maka $n$ dapat difaktorkan sebagai darab dari dua bilangan berbeda, yaitu $n=ab$ , dengan $2\leq a<b<n$ . Akibatnya, $a$ dan $b$ akan muncul sebagai faktor dari $(n-1)!=(n-1)\times (n-2)\times \ldots \times 3\times 2\times 1$ , sehingga $(n-1)!$ habis dibagi oleh $ab$ .

Modulus Prima

Dua pembuktian berikut menggunakan fakta bahwa kelas-kelas residu modulo bilangan prima merupakan suatu lapangan—lebih tepatnya, medan prima hingga.^[7]

Bukti elementer

Untuk $p=2$ , hasil dari teorema Wilson bersifat trivial, sehingga diasumsikan bahwa $p$ adalah bilangan prima ganjil. Oleh karena kelas-kelas residu modulo $p$ merupakan lapangan, maka setiap residu tak nol $a$ memiliki invers perkalian $a^{-1}$ yang bersifat tunggal. Jika $a\equiv a^{-1}{\pmod {p}}$ , maka ${\begin{aligned}a&\equiv a^{-1}&{\pmod {p}}\\a^{2}&\equiv 1&{\pmod {p}}\\a^{2}-1&\equiv 0&{\pmod {p}}\\p&\mid (a^{2}-1)\\p&\mid (a-1)(a+1)\end{aligned}}$ sehingga berdasarkan lema Euclid, maka nilai $a$ yang memenuhi $a\equiv a^{-1}{\pmod {p}}$ ialah $a\equiv \pm 1{\pmod {p}}$ . Akibatnya, setiap faktor selain $\pm 1$ dari $(p-1)!$ dapat disusun ulang menjadi ${\tfrac {p-3}{2}}$ pasangan sedemikian sehingga darab dari setiap pasangan akan kongruen dengan 1 modulo $p$ . Alhasil, teorema Wilson terbukti.

Sebagai contoh, untuk $p=11$ , maka perhatikan bahwa $10!=(1\cdot 10)\cdot (2\cdot 6)\cdot (3\cdot 4)\cdot (5\cdot 9)\cdot (7\cdot 8)\equiv (-1)\cdot 1\cdot 1\cdot 1\cdot 1\equiv -1{\pmod {11}}$

Bukti menggunakan teorema kecil Fermat

Untuk $p=2$ , hasil dari teorema Wilson bersifat trivial, sehingga diasumsikan bahwa $p$ adalah bilangan prima ganjil. Pandang polinomial berikut $f(x)=(x-1)(x-2)(x-3)\ldots (x-(p-1))$ Perhatikan bahwa $f$ memiliki derajat $p-1$ , dengan suku utama $x^{p-1}$ serta konstanta $(p-1)!$ . Nilai-nilai pembuat nol dari $f$ ialah $\left\{1,\,2,\,3,\,\ldots ,\,p-1\right\}$ .

Selanjutnya, pandang polinomial $g(x)=x^{p-1}-1$ Perhatikan bahwa $g$ memiliki derajat $p-1$ , dengan suku utama $x^{p-1}$ . Oleh karena $p$ prima, maka setiap bilangan pada $\left\{1,\,2,\,3,\,\ldots ,\,p-1\right\}$ akan relatif prima dengan $p$ . Berdasarkan teorema kecil Fermat, maka pembuat nol dari $g$ dalam modulo $p$ ialah $\left\{1,\,2,\,3,\,\ldots ,\,p-1\right\}$ .

Terakhir, pandang fungsi $h(x)=f(x)-g(x)$ Perhatikan bahwa $h$ memiliki derajat paling tinggi $p-2$ (sebab suku utama dari $f$ dan $g$ saling meniadakan) dan pembuat nol dari $h$ ialah $\left\{1,\,2,\,3,\,\ldots ,\,p-1\right\}$ . Akan tetapi, $h$ tidak mungkin memiliki lebih dari $n-2$ akar, berdasarkan teorema Lagrange. Akibatnya, $h$ haruslah identik nol dalam modulo $p$ . Dengan memandang konstanta pada polinomial $h$ , maka diperoleh

$(p-1)!+1\equiv 0{\pmod {p}}$

Penerapan

Uji keprimaan

Pada penerapannya, teorema Wilson tidak berguna sebagai uji keprimaan, sebab perhitungan nilai $(n-1)!$ modulo $n$ merupakan hal yang berat secara komputasional untuk bilangan $n$ yang besar.^[8]^[9]

Residu kuadratik

Dengan menggunakan teorema Wilson, maka untuk setiap bilangan prima ganjil $p=2n+1$ , ruas kiri dari

$1\cdot 2\cdot 3\cdot \ldots \cdot (p-1)\equiv -1{\pmod {p}}$

dapat disusun ulang sebagai berikut

${\begin{aligned}1\cdot (p-1)\cdot 2\cdot (p-2)\cdot 3\cdot (p-3)\cdot \ldots \cdot n\cdot (p-n)&\equiv -1&&{\pmod {p}}\\1\cdot (-1)\cdot 2\cdot (-2)\cdot 3\cdot (-3)\cdot \ldots \cdot n\cdot (-n)&\equiv -1&&{\pmod {p}}\end{aligned}}$

sehingga didapatkan

${\begin{aligned}\prod _{k\,=\,1}^{n}\left(-1\right)^{n}k^{2}&\equiv -1&&{\pmod {p}}\\\prod _{k\,=\,1}^{n}k^{2}&\equiv \left(-1\right)^{n+1}&&{\pmod {p}}\\(n!)^{2}&\equiv \left(-1\right)^{n+1}&&{\pmod {p}}\end{aligned}}$

Informasi ini dapat digunakan untuk membuktikan teorema terkenal:

Teorema — Untuk setiap bilangan prima $p$ yang memenuhi $p\equiv 1{\pmod {4}}$ , bilangan $-1$ merupakan persegi (residu kuadratik) modulo $p$ .

Bukti —

Untuk membuktikannya, diambil sembarang bilangan prima $p=4N+1$ , dengan $N\in \mathbb {N}$ . Dengan memilih $n=2N$ pada bentuk di atas, maka dapat disimpulkan bahwa $(n!)^{2}$ kongruen dengan $-1$ dalam modulo $p$ .

Persamaan untuk bilangan prima

Teorema Wilson telah digunakan untuk mengonstruksikan rumus bilangan prima. Namun, pendekatan tersebut terlalu lambat untuk kegunaan praktis.

Fungsi gamma $p$ -adik

Teorema Wilson dapat digunakan untuk mendefinisikan fungsi gamma $p$ -adik.

Generalisasi Gauss

Gauss membuktikan bahwa^[10]^[11]

$\prod _{k\,=\,1 \atop \operatorname {FPB} (n,\,k)\,=\,1}^{n-1}\!\!\!\!k\,\equiv {\begin{cases}-1{\pmod {n}}&{\text{jika}}\;n=4,\;p^{N},\;2p^{N}\\{\phantom {-}}1{\pmod {n}}&{\text{lainnya}}\end{cases}}$

dengan $p$ menyatakan bilangan prima ganjil, dan $N\in \mathbb {N}$ . Dengan kata lain, darab dari semua bilangan asli yang kurang dari $n$ dan relatif prima dengan $n$ ialah satu kurangnya suatu kelipatan $n$ ketika $n$ sama dengan 4, atau perpangkatan suatu bilangan prima ganjil, atau dua kalinya perpangkatan suatu bilangan prima ganjil; untuk nilai-nilai lainnya, hasil darabnya ialah satu lebihnya suatu kelipatan $n$ .

Lihat juga

Catatan

↑ Darling, David J. The Universal Book of Mathematics [Buku Matematika Universal] (dalam bahasa Inggris). hlm. 350. ISBN 978-0-471-27047-8.
↑ "Ibn al-Haytham - Biography" [Ibnu al-Haitsam - Biografi]. Maths History (dalam bahasa Inggris). Diakses tanggal 10 Februari 2021.
↑ Waring, Edward (1770). Meditationes Algebraicae (dalam bahasa Latin). hlm. 218. Dalam edisi ketiga (1782) dari Meditationes Algebraicae karya Waring, teorema Wilson muncul sebagai soal ke-5 pada halaman 380. Pada halaman tersebut, Waring menyatakan "Hanc maxime elegantem primorum numerorum proprietatem invenit vir clarissimus, rerumque mathematicarum peritissimus Joannes Wilson Armiger." (Seorang pria yang paling terkemuka dan paling ahli dalam matematika, Squire John Wilson, menemukan sifat yang paling elegan dari bilangan prima.)
↑ Lagrange, Joseph Louis (1773). Démonstration d’un Théorème nouveau concernant les nombres premiers [Bukti teorema baru mengenai bilangan prima] (dalam bahasa Prancis). Vol. 2. hlm. 125–137.
↑ Vacca, Giovanni (1899). "Sui manoscritti inediti di Leibniz" [Manuskrip Leibniz yang tidak terpublikasikan]. Bollettino di bibliografia e storia delle scienze matematiche (dalam bahasa Italia). 2: 113–116. Vacca mengutip dari manuskrip matematika Leibniz yang disimpan pada Royal Public Library di Hannover (Jerman), vol. 3 B, halaman 10:
Orisinal : Inoltre egli intravide anche il teorema di Wilson, come risulta dall'enunciato seguente:
"Productus continuorum usque ad numerum qui antepraecedit datum divisus per datum relinquit 1 (vel complementum ad unum?) si datus sit primitivus. Si datus sit derivativus relinquet numerum qui cum dato habeat communem mensuram unitate majorem."
Egli non giunse pero a dimostrarlo.
↑ Peano, Giuseppe (1897). Formulaire de mathématiques: t. I-V (dalam bahasa Prancis). Vol. 2. Bocca frères, Ch. Clausen. hlm. 85.
↑ Landau, Edmund (1966) [1927]. "Part One, Chapter V: Congruences, Theorem 77" [Bagian 1, Bab V: Kekongruenan, Teorema 77]. Elementary Number Theory [Teori Bilangan Elementer] (dalam bahasa Inggris) (Edisi 2). New York: Chelsea Publishing Company. hlm. 51–52. LCCN 66002147. OCLC 1420155. OL 5976039M. Diakses tanggal 6 Februari 2025.
↑ (Lagrange 1773, hlm. 132)
↑ Lagrange, p. 132: "cette méthode devient extrémement laborieuse, & presque impracticable"
↑ Gauss, DA, art. 78
↑ Cosgrave, John B.; Dilcher, Karl (2008). "Extensions of the Gauss–Wilson theorem" [Perluasan dari teorema Gauss–Wilson]. Integers (dalam bahasa Inggris). 8 A39. MR 2472057.

Referensi

Disquisitiones Arithmeticae telah diterjemahkan dari bahasa Latin Ciceronian Gauss ke dalam bahasa Inggris dan Jerman. Edisi Jerman mencakup semua paper teori bilangan miliknya: semua bukti dari timbal balik kuadratik, penentuan tanda dari jumlah Gauss, penyelidikan timbal balik bikuadratik, serta catatan yang tidak diterbitkan.

Terjemahan bahasa Inggris: Gauss, Carl Friedrich (1986). Disquisitiones Arithemeticae. Diterjemahkan oleh Clarke, Arthur A. (Edisi kedua, telah diperbaiki). New York: Springer. ISBN 0-387-96254-9.
Terjemahan bahasa Jerman: Gauss, Carl Friedrich (1965). Untersuchungen uber hohere Arithmetik (Disquisitiones Arithemeticae & paper lainnya dalam teori bilangan). Diterjemahkan oleh Maser, H. (Edisi 2). New York: Chelsea. ISBN 0-8284-0191-8.
Landau, Edmund (1966), Elementary Number Theory [Teori Bilangan Elementer] (dalam bahasa Inggris), New York: Chelsea
Ore, Øystein (1988). Number Theory and its History [Teori Bilangan beserta Sejarahnya] (dalam bahasa Inggris). Dover. hlm. 259–271. ISBN 0-486-65620-9.

Pranala luar

Hazewinkel, Michiel, ed. (2001) [1994], "Teorema Wilson", Encyclopedia of Mathematics, Springer Science+Business Media B.V. / Kluwer Academic Publishers, ISBN 978-1-55608-010-4
Weisstein, Eric W. "Teorema Wilson". MathWorld.
(Inggris) Bukti sistem Mizar : http://mizar.org/version/current/html/nat_5.html#T22
Ohana, Andrew. "A Generalization of Wilson's Theorem" [Perumuman Teorema Wilson] (PDF) (dalam bahasa Inggris).

[1] Darling, David J. The Universal Book of Mathematics [Buku Matematika Universal] (dalam bahasa Inggris). hlm. 350. ISBN 978-0-471-27047-8.

[2] "Ibn al-Haytham - Biography" [Ibnu al-Haitsam - Biografi]. Maths History (dalam bahasa Inggris). Diakses tanggal 10 Februari 2021.

[3] Waring, Edward (1770). Meditationes Algebraicae (dalam bahasa Latin). hlm. 218. Dalam edisi ketiga (1782) dari Meditationes Algebraicae karya Waring, teorema Wilson muncul sebagai soal ke-5 pada halaman 380. Pada halaman tersebut, Waring menyatakan "Hanc maxime elegantem primorum numerorum proprietatem invenit vir clarissimus, rerumque mathematicarum peritissimus Joannes Wilson Armiger." (Seorang pria yang paling terkemuka dan paling ahli dalam matematika, Squire John Wilson, menemukan sifat yang paling elegan dari bilangan prima.)

[4] Lagrange, Joseph Louis (1773). Démonstration d’un Théorème nouveau concernant les nombres premiers [Bukti teorema baru mengenai bilangan prima] (dalam bahasa Prancis). Vol. 2. hlm. 125–137.

[5] Vacca, Giovanni (1899). "Sui manoscritti inediti di Leibniz" [Manuskrip Leibniz yang tidak terpublikasikan]. Bollettino di bibliografia e storia delle scienze matematiche (dalam bahasa Italia). 2: 113–116. Vacca mengutip dari manuskrip matematika Leibniz yang disimpan pada Royal Public Library di Hannover (Jerman), vol. 3 B, halaman 10:
Orisinal : Inoltre egli intravide anche il teorema di Wilson, come risulta dall'enunciato seguente:
"Productus continuorum usque ad numerum qui antepraecedit datum divisus per datum relinquit 1 (vel complementum ad unum?) si datus sit primitivus. Si datus sit derivativus relinquet numerum qui cum dato habeat communem mensuram unitate majorem."
Egli non giunse pero a dimostrarlo.

[6] Peano, Giuseppe (1897). Formulaire de mathématiques: t. I-V (dalam bahasa Prancis). Vol. 2. Bocca frères, Ch. Clausen. hlm. 85.

[7] Landau, Edmund (1966) [1927]. "Part One, Chapter V: Congruences, Theorem 77" [Bagian 1, Bab V: Kekongruenan, Teorema 77]. Elementary Number Theory [Teori Bilangan Elementer] (dalam bahasa Inggris) (Edisi 2). New York: Chelsea Publishing Company. hlm. 51–52. LCCN 66002147. OCLC 1420155. OL 5976039M. Diakses tanggal 6 Februari 2025.

[8] (Lagrange 1773, hlm. 132)

[9] Lagrange, p. 132: "cette méthode devient extrémement laborieuse, & presque impracticable"

[10] Gauss, DA, art. 78

[11] Cosgrave, John B.; Dilcher, Karl (2008). "Extensions of the Gauss–Wilson theorem" [Perluasan dari teorema Gauss–Wilson]. Integers (dalam bahasa Inggris). 8 A39. MR 2472057.

[1]