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 \dots \times (n - 1)$ akan memenuhi relasi kekongruenan

$(n - 1)! \equiv - 1 (\mod 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 .^[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 mod 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)!$	$(n - 1)! mod n$
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 ℤ$ sedemikian sehingga $n = p k$ . Misalkandengan dalih untuk mencari kontradiksinilai $(n - 1)!$ kongruen dengan $- 1$ dalam modulo $n$ . Perhatikan bahwa $(n - 1)! + 1 = n N = (p k) N = p (k N)$ untuk suatu $N \in ℕ$ . 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 \dots \times 3 \times 2 \times 1$ ialah $p$ , sehingga $(n - 1)! \equiv 0 (\mod p)$ . Oleh karena terjadi kontradiksi, maka asumsi di awalbahwa 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 (\mod 4)$ . Bukti dari pernyataan tersebut dapat dibagi menjadi dua kasus:

Jika $n$ merupakan kuadrat dari suatu bilangan prima $q > 2$ , maka $\begin{matrix} 2 & < q \\ 2 q & < q^{2} = n \\ 2 q & < n \\ 2 < q < 2 q & < n \end{matrix}$ Akibatnya, $q$ dan $2 q$ akan muncul sebagai faktor dari $(n - 1)! = (n - 1) \times (n - 2) \times \dots \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 = a b$ , dengan $2 \leq a < b < n$ . Akibatnya, $a$ dan $b$ akan muncul sebagai faktor dari $(n - 1)! = (n - 1) \times (n - 2) \times \dots \times 3 \times 2 \times 1$ , sehingga $(n - 1)!$ habis dibagi oleh $a b$ .

Modulus Prima

Dua pembuktian berikut menggunakan fakta bahwa kelas-kelas residu modulo bilangan prima merupakan suatu lapanganlebih 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} (\mod p)$ , maka $\begin{matrix} a & \equiv a^{- 1} & (\mod p) \\ a^{2} & \equiv 1 & (\mod p) \\ a^{2} - 1 & \equiv 0 & (\mod p) \\ p & ∣ (a^{2} - 1) \\ p & ∣ (a - 1) (a + 1) \end{matrix}$ sehingga berdasarkan lema Euclid, maka nilai $a$ yang memenuhi $a \equiv a^{- 1} (\mod p)$ ialah $a \equiv \pm 1 (\mod p)$ . Akibatnya, setiap faktor selain $\pm 1$ dari $(p - 1)!$ dapat disusun ulang menjadi $\frac{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 (\mod 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) \dots (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 ${1, 2, 3, \dots, p - 1}$ .

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 ${1, 2, 3, \dots, p - 1}$ akan relatif prima dengan $p$ . Berdasarkan teorema kecil Fermat, maka pembuat nol dari $g$ dalam modulo $p$ ialah ${1, 2, 3, \dots, p - 1}$ .

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 ${1, 2, 3, \dots, p - 1}$ . 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 (\mod 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 = 2 n + 1$ , ruas kiri dari

$1 \cdot 2 \cdot 3 \cdot \dots \cdot (p - 1) \equiv - 1 (\mod p)$

dapat disusun ulang sebagai berikut

$\begin{matrix} 1 \cdot (p - 1) \cdot 2 \cdot (p - 2) \cdot 3 \cdot (p - 3) \cdot \dots \cdot n \cdot (p - n) & \equiv - 1 & (\mod p) \\ 1 \cdot (- 1) \cdot 2 \cdot (- 2) \cdot 3 \cdot (- 3) \cdot \dots \cdot n \cdot (- n) & \equiv - 1 & (\mod p) \end{matrix}$

sehingga didapatkan

$\begin{matrix} \prod_{k = 1}^{n} {(- 1)}^{n} k^{2} & \equiv - 1 & (\mod p) \\ \prod_{k = 1}^{n} k^{2} & \equiv {(- 1)}^{n + 1} & (\mod p) \\ (n!)^{2} & \equiv {(- 1)}^{n + 1} & (\mod p) \end{matrix}$

Informasi ini dapat digunakan untuk membuktikan teorema terkenal:

Persamaan untuk bilangan prima

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

Fungsi gamma -adik

Teorema Wilson dapat digunakan untuk mendefinisikan fungsi gamma -adik.

Generalisasi Gauss

Gauss membuktikan bahwa^[10]^[11]

$\prod_{\binom{k = 1}{FPB (n, k) = 1}}^{n - 1} k \equiv {\begin{matrix} - 1 (\mod n) & jika n = 4, p^{N}, 2 p^{N} \\ 1 (\mod n) & lainnya \end{matrix}$

dengan $p$ menyatakan bilangan prima ganjil, dan $N \in ℕ$ . 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

Pranala luar

Bukti sistem Mizar : http://mizar.org/version/current/html/nat_5.html#T22

Referensi

↑ David J. Darling. The Universal Book of Mathematics. hlm. 350. ISBN 978-0-471-27047-8.
↑ Ibn al-Haytham - Biography. Maths History.
↑ Edward Waring. Meditationes Algebraicae. 1770. 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.)
↑ Joseph Louis Lagrange. Démonstration d’un Théorème nouveau concernant les nombres premiers. 1773. Vol. 2. hlm. 125–137.
↑ Giovanni Vacca. Sui manoscritti inediti di Leibniz. Bollettino di bibliografia e storia delle scienze matematiche. 1899. Vol. 2. hlm. 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.
↑ Giuseppe Peano. Formulaire de mathématiques: t. I-V. Bocca frères, Ch. Clausen. 1897. Vol. 2. hlm. 85.
↑ Edmund Landau. Elementary Number Theory. Chelsea Publishing Company. 1966. hlm. 51–52.
↑ sumber pada Wikipedia bahasa Indonesia
↑ Lagrange, p. 132: "cette méthode devient extrémement laborieuse, & presque impracticable"
↑ Gauss, DA, art. 78
↑ John B. Cosgrave. Extensions of the Gauss–Wilson theorem. Integers. 2008. Vol. 8.

Sumber dan atribusi

Konten artikel ini diadaptasi dari Wikipedia bahasa Indonesia, revisi 29455005 (2026-07-14T00:09:15Z), yang tersedia berdasarkan lisensi Creative Commons Atribusi-BerbagiSerupa (CC BY-SA). Mohon gunakan konten ini secara bijak serta sesuai dengan ketentuan lisensi yang berlaku.

[1] David J. Darling. The Universal Book of Mathematics. hlm. 350. ISBN 978-0-471-27047-8.

[2] Ibn al-Haytham - Biography. Maths History.

[3] Edward Waring. Meditationes Algebraicae. 1770. 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] Joseph Louis Lagrange. Démonstration d’un Théorème nouveau concernant les nombres premiers. 1773. Vol. 2. hlm. 125–137.

[5] Giovanni Vacca. Sui manoscritti inediti di Leibniz. Bollettino di bibliografia e storia delle scienze matematiche. 1899. Vol. 2. hlm. 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] Giuseppe Peano. Formulaire de mathématiques: t. I-V. Bocca frères, Ch. Clausen. 1897. Vol. 2. hlm. 85.

[7] Edmund Landau. Elementary Number Theory. Chelsea Publishing Company. 1966. hlm. 51–52.

[8] sumber pada Wikipedia bahasa Indonesia

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

[10] Gauss, DA, art. 78

[11] John B. Cosgrave. Extensions of the Gauss–Wilson theorem. Integers. 2008. Vol. 8.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]