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 \times2 \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.

## Sejarah
Teorema ini dinyatakan oleh Ibnu al-Haitsam . Edward Waring mengumumkan teorema tersebut pada tahun 1770 tanpa membuktikannya. Ia mengatributkan muridnya, John Wilson, atas penemuan tersebut. Langrage memberikan bukti pertama pada tahun 1771. Terdapat bukti bahwa Leibniz juga menyadari kebenaran teorema tersebut satu abad sebelumnya, tetapi ia tidak pernah menerbitkannya.

## 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.

## 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 . Oleh karena p habis membagi n, maka terdapat suatu k \in \mathbb{Z} sedemikian sehingga n = pk. Misalkandengan dalih untuk mencari kontradiksinilai (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 awalbahwa nilai (n - 1)! kongruen dengan -1 dalam modulo ntidak 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{align}
2 & 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 . 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 lapanganlebih tepatnya, medan prima hingga.

#### 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{align}
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{align}
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.

### 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{align}
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{align}

sehingga didapatkan

\begin{align}
\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{align}

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


\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
* Bilangan prima Wilson
* Tabel kekongruenan
* Konjektur Agoh–Giuga

## Catatan

## 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: 
* Terjemahan bahasa Jerman: 
* 
* 

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