Bukti 1

Pembuktian ini menggunakan fakta bahwa kelas-kelas residu modulo suatu bilangan prima membentuk struktur aljabar lapangan. Lihat artikel grup perkalian bilangan bulat modulo n untuk pembahasan lebih lanjut.

Diambil sembarang bilangan prima ganjil ${\displaystyle p}$ dan sembarang bilangan bulat ${\displaystyle a}$ yang relatif prima dengan ${\displaystyle p}$. Pertama, akan dibuktikan bahwa terdapat ${\displaystyle {\tfrac {p-1}{2}}}$ nilai residu kuadratik tak nol berbeda dalam himpunan bilangan bulat modulo ${\displaystyle p}$.

Diketahui bahwa ${\displaystyle a}$ relatif prima dengan ${\displaystyle p}$, maka berdasarkan teorema kecil Fermat, berlaku $${\displaystyle a^{p-1}\equiv 1{\pmod {p}}}$$ yang dapat ditulis menjadi $${\displaystyle \left(a^{\tfrac {p-1}{2}}-1\right)\left(a^{\tfrac {p-1}{2}}+1\right)\equiv 0{\pmod {p}}}$$ sebab ${\displaystyle p}$ merupakan bilangan ganjil. Oleh karena himpunan bilangan bulat modulo ${\displaystyle p}$ merupakan lapangan, maka salah satu dari kedua faktor tersebut harus kongruen dengan nol. Dengan kata lain, berlaku $${\displaystyle a^{\tfrac {p-1}{2}}\equiv 1{\pmod {p}}\qquad \qquad {\text{atau}}\qquad \qquad a^{\tfrac {p-1}{2}}\equiv -1{\pmod {p}}}$$

Jika ${\displaystyle a}$ merupakan residu kuadratik modulo ${\displaystyle p}$, maka terdapat suatu ${\displaystyle k\in \mathbb {Z} }$ sedemikian sehingga ${\displaystyle k^{2}\equiv a{\pmod {p}}}$. Diketahui bahwa ${\displaystyle a}$ relatif prima dengan ${\displaystyle p}$, maka ${\displaystyle k}$ juga relatif prima dengan ${\displaystyle p}$. Akibatnya, $${\displaystyle a^{\tfrac {p-1}{2}}\equiv (k^{2})^{\tfrac {p-1}{2}}=k^{p-1}\equiv 1{\pmod {p}}}$$ Dengan kata lain, setiap residu kuadratik modulo ${\displaystyle p}$ akan membuat nilai dari faktor pertama menjadi nol. Berdasarkan teorema Lagrange, maka kekongruenan ${\displaystyle x^{\tfrac {p-1}{2}}\equiv 1{\pmod {p}}}$ memiliki paling banyak ${\displaystyle {\tfrac {p-1}{2}}}$ penyelesaian, sehingga dapat disimpulkan bahwa ${\displaystyle {\tfrac {p-1}{2}}}$ kelas residu lainnya (yaitu nilai-nilai nonresidu kuadratik modulo ${\displaystyle p}$) harus membuat nilai dari faktor kedua menjadi nol. Inilah isi dari kriteria Euler.

Bukti 2

Diambil sembarang bilangan prima ganjil ${\displaystyle p}$ dan sembarang bilangan bulat ${\displaystyle a}$ yang relatif prima dengan ${\displaystyle p}$. Akan ditinjau dua kasus berikut:

1. Jika ${\displaystyle a}$ merupakan residu kuadratik modulo ${\displaystyle p}$, maka berdasarkan definisi, terdapat suatu bilangan bulat ${\displaystyle n}$ sedemikian sehingga $${\displaystyle n^{2}\equiv a{\pmod {p}}}$$ Oleh karena ${\displaystyle a}$ relatif prima dengan ${\displaystyle p}$, maka ${\displaystyle n}$ juga relatif prima dengan ${\displaystyle p}$, sehingga berdasarkan teorema kecil Fermat, berlaku $${\displaystyle 1\equiv n^{p-1}=(n^{2})^{\tfrac {p-1}{2}}\equiv a^{\tfrac {p-1}{2}}{\pmod {p}}}$$
2. Perhatikan bahwa untuk setiap ${\displaystyle n\in \left\{1,\,2,\,3,\,\ldots ,\,p-1\right\}}$, maka berlaku ${\displaystyle \operatorname {FPB} (n,\,p)=1}$. Akibatnya, terdapat tepat satu nilai ${\displaystyle n'\in \left\{1,\,2,\,3,\,\ldots ,\,p-1\right\}}$ sedemikian sehingga $${\displaystyle n\cdot n'\equiv a{\pmod {p}}}$$ Diketahui bahwa ${\displaystyle a}$ merupakan nonresidu kuadratik modulo ${\displaystyle p}$, maka nilai ${\displaystyle n'\neq n}$. Alhasil, setiap komponen dari darab $${\displaystyle 1\cdot 2\cdot 3\cdot \ldots \cdot (p-1)}$$ dapat disusun ulang menjadi ${\displaystyle {\tfrac {p-1}{2}}}$ pasangan sedemikian sehingga darab dari setiap pasangan akan kongruen dengan ${\displaystyle a}$ dalam modulo ${\displaystyle p}$. Dengan menggunakan notasi faktorial serta teorema Wilson, maka $${\displaystyle a^{\tfrac {p-1}{2}}\equiv (p-1)!\equiv -1{\pmod {p}}}$$

Bukti 3

Bukti ini merupakan modifikasi dari Bukti 2, dan dapat digunakan untuk membuktikan teorema Wilson, kriteria Euler, dan teorema kecil Fermat sekaligus.

Diambil sembarang bilangan prima ganjil ${\displaystyle p}$ dan sembarang bilangan bulat ${\displaystyle a}$ yang relatif prima dengan ${\displaystyle p}$. Didefinisikan himpunan ${\displaystyle \mathbb {Z} _{p}}$ sebagai ${\displaystyle \left\{1,\,2,\,3,\,\ldots ,\,p-1\right\}}$. Perhatikan bahwa untuk setiap ${\displaystyle k\in \mathbb {Z} _{p}}$, maka berlaku ${\displaystyle \operatorname {FPB} (k,\,p)=1}$. Akibatnya, terdapat tepat satu nilai ${\displaystyle k'\in \mathbb {Z} _{p}}$ sedemikian sehingga ${\displaystyle k\cdot k'\equiv a{\pmod {p}}}$.

1. Jika ${\displaystyle a}$ merupakan nonresidu kuadratik, maka nilai ${\displaystyle k'\neq k}$ untuk setiap nilai ${\displaystyle k\in \mathbb {Z} _{p}}$. Alhasil, semua elemen dari himpunan ${\displaystyle \mathbb {Z} _{p}}$ dapat dikelompokkan menjadi ${\displaystyle {\tfrac {p-1}{2}}}$ pasangan sedemikian sehingga darab dari setiap pasangan akan kongruen dengan ${\displaystyle a}$ dalam modulo ${\displaystyle p}$. Dengan menggunakan notasi faktorial serta simbol Legendre, maka $${\displaystyle (p-1)!\equiv a^{\tfrac {p-1}{2}}\equiv -\left({\dfrac {a}{p}}\right)\cdot a^{\tfrac {p-1}{2}}{\pmod {p}}}$$
2. Jika ${\displaystyle a}$ merupakan residu kuadratik, maka berdasarkan definisi, terdapat suatu bilangan bulat ${\displaystyle n}$ sedemikian sehingga $${\displaystyle n^{2}\equiv a{\pmod {p}}}$$ Lebih lanjut, ${\displaystyle (p-n)^{2}}$ juga kongruen dengan ${\displaystyle a}$ dalam modulo ${\displaystyle p}$, sebab $${\displaystyle (p-n)^{2}\equiv p^{2}-2pn+n^{2}\equiv n^{2}\equiv a{\pmod {p}}}$$ Berdasarkan teorema Lagrange, maka kekongruenan ${\displaystyle x^{2}\equiv a{\pmod {p}}}$ memiliki paling banyak 2 penyelesaian pada himpunan ${\displaystyle \mathbb {Z} _{p}}$. Dengan kata lain, tidak ada nilai ${\displaystyle x\in \mathbb {Z} _{p}}$ selain ${\displaystyle x=n}$ dan ${\displaystyle x=p-n}$ yang memenuhi kekongruenan tersebut. Akibatnya, ${\displaystyle p-3}$ bilangan pada himpunan ${\displaystyle \mathbb {Z} _{p}\setminus \left\{n,\,p-n\right\}}$ dapat dikelompokkan menjadi ${\displaystyle {\tfrac {p-3}{2}}}$ pasangan sedemikian sehingga darab dari setiap pasangan akan kongruen dengan ${\displaystyle a}$ dalam modulo ${\displaystyle p}$. Oleh karena ${\displaystyle n\cdot (p-n)\equiv -a{\pmod {p}}}$, maka dengan menggunakan notasi faktorial serta simbol Legendre, diperoleh $${\displaystyle (p-1)!\equiv -a\cdot a^{\tfrac {p-3}{2}}\equiv -\left({\dfrac {a}{p}}\right)\cdot a^{\tfrac {p-1}{2}}{\pmod {p}}}$$

Berdasarkan kedua kasus di atas, maka untuk setiap nilai ${\displaystyle a}$ yang relatif prima dengan ${\displaystyle p}$, maka berlaku $${\displaystyle (p-1)!\equiv -\left({\dfrac {a}{p}}\right)\cdot a^{\tfrac {p-1}{2}}{\pmod {p}}}$$ Jika ${\displaystyle a=1}$, maka jelas bahwa ${\displaystyle \left({\dfrac {a}{p}}\right)=1}$, sehingga didapatkan satu arah dari teorema Wilson, yaitu $${\displaystyle (p-1)!\equiv -1{\pmod {p}}}$$ Akibatnya, berlaku $${\displaystyle {\begin{aligned}(p-1)!&\equiv -\left({\dfrac {a}{p}}\right)\cdot a^{\tfrac {p-1}{2}}{\pmod {p}}\\-1&\equiv -\left({\dfrac {a}{p}}\right)\cdot a^{\tfrac {p-1}{2}}{\pmod {p}}\\1&\equiv \left({\dfrac {a}{p}}\right)\cdot a^{\tfrac {p-1}{2}}{\pmod {p}}\\\left({\dfrac {a}{p}}\right)&\equiv \left({\dfrac {a}{p}}\right)^{2}\cdot a^{\tfrac {p-1}{2}}{\pmod {p}}\\\left({\dfrac {a}{p}}\right)&\equiv a^{\tfrac {p-1}{2}}{\pmod {p}}\end{aligned}}}$$ yang merupakan isi pernyataan dari kriteria Euler. Jika kedua ruas dari kekongruenan tersebut dikuadratkan, maka teorema kecil Fermat terbukti: $${\displaystyle {\begin{aligned}\left({\dfrac {a}{p}}\right)&\equiv a^{\tfrac {p-1}{2}}{\pmod {p}}\\\left({\dfrac {a}{p}}\right)^{2}&\equiv \left(a^{\tfrac {p-1}{2}}\right)^{2}{\pmod {p}}\\1&\equiv a^{p-1}{\pmod {p}}\end{aligned}}}$$

Mencari modulus jika diberikan nilai residu

Bilangan prima ${\displaystyle p}$ mana saja yang menjadikan 17 sebagai residu kuadratik?

Dalam kasus ini, nilai ${\displaystyle p}$ dapat diperiksa secara manual menggunakan kriteria Euler.

• Untuk ${\displaystyle p=13}$, maka $${\displaystyle 17^{\tfrac {13-1}{2}}=17^{6}\equiv 4^{6}=64^{2}\equiv (-1)^{2}=1{\pmod {13}}}$$ sehingga dapat disimpulkan bahwa 17 merupakan residu kuadratik modulo 13. Sebagai konfirmasi, perhatikan bahwa ${\displaystyle 17\equiv 4=2^{2}{\pmod {13}}}$.
• Untuk ${\displaystyle p=11}$, maka $${\displaystyle 17^{\tfrac {11-1}{2}}=17^{5}\equiv 6^{5}\equiv 3^{2}\cdot 6\equiv -1{\pmod {11}}}$$ sehingga dapat disimpulkan bahwa 17 merupakan nonresidu kuadratik modulo 11.

Jika proses pemeriksaan ini terus dilanjutkan, maka diperoleh $${\displaystyle \left({\dfrac {17}{p}}\right)={\begin{cases}\;\;\,1{\pmod {p}}&{\text{untuk}}\;p\in \left\{13,\,19,\,43,\,\ldots \right\}\\-1{\pmod {p}}&{\text{untuk}}\;p\in \left\{3,\,5,\,7,\,11,\,23,\,\ldots \right\}\end{cases}}}$$

Mencari residu jika diberikan nilai modulus

Tentukan semua bilangan persegi (semua residu kuadratik) pada modulo 17.

Dalam kasus ini, maka residu kuadratik modulo 17 dapat dicari secara manual sebagai berikut:

• ${\displaystyle 1^{2}=1{\pmod {17}}}$
• ${\displaystyle 2^{2}=4{\pmod {17}}}$
• ${\displaystyle 3^{2}=9{\pmod {17}}}$
• ${\displaystyle 4^{2}=16{\pmod {17}}}$
• ${\displaystyle 5^{2}=25\equiv 8{\pmod {17}}}$
• ${\displaystyle 6^{2}=36\equiv 2{\pmod {17}}}$
• ${\displaystyle 7^{2}=49\equiv 15{\pmod {17}}}$
• ${\displaystyle 8^{2}=64\equiv 13{\pmod {17}}}$

sehingga himpunan emua residu kuadratik modulo 17 ialah ${\displaystyle R_{17}=\left\{1,\,2,\,4,\,8,\,9,\,13,\,15,\,16\right\}}$. Perhatikan bahwa kuadrat dari 9–16 tidak perlu dihitung, sebab setiap bilangan mulai dari 9 sampai dengan 16 kongruen dengan negatif dari 1 sampai dengan 8 dalam modulo 17. Misalnya, ${\displaystyle 11\equiv -6{\pmod {17}}}$, sehingga ${\displaystyle 11^{2}\equiv (-6)^{2}=36\equiv 2{\pmod {17}}}$.

Kriteria Euler dapat digunakan untuk mencari atau memverifikasi residu kuadratik. Misalnya,

• Untuk memeriksa apakah 14 merupakan residu kuadratik modulo 17, maka berdasarkan kriteria Euler, $${\displaystyle 14^{\tfrac {17-1}{2}}=14^{8}\equiv (-3)^{8}=81^{2}\equiv (-4)^{2}=16\equiv -1{\pmod {17}}}$$ sehingga dapat disimpulkan bahwa 14 merupakan nonresidu kuadratik (yang sesuai dengan hasil di atas, yaitu ${\displaystyle 14\not \in R_{17}}$)
• Untuk memeriksa apakah 15 merupakan residu kuadratik modulo 17, maka berdasarkan kriteria Euler, $${\displaystyle 15^{\tfrac {17-1}{2}}=15^{8}\equiv (-2)^{8}=16^{2}\equiv (-1)^{2}=1{\pmod {17}}}$$ sehingga dapat disimpulkan bahwa 15 merupakan residu kuadratik (yang sesuai dengan hasil di atas, yaitu ${\displaystyle 15\in R_{17}}$)