Kriteria Euler

Dalam teori bilangan, **kriteria Euler** adalah rumus untuk menentukan apakah suatu bilangan bulat merupakan residu kuadratik modulo suatu bilangan prima. Lebih tepatnya,

 \equiv \begin{cases}
\; \; \, 1 \pmod{p} & \text{Jika terdapat suatu bilangan bulat} \; n \; \text{sedemikian sehingga} \; n^2 \equiv a \pmod{p} \\
-1 \pmod{p} & \text{Jika tidak terdapat bilangan bulat yang memenuhi kekongruenan tersebut}
\end{cases}}}

Kriteria Euler dapat dirumuskan menggunakan simbol Legendre sebagai berikut:

\left( \dfrac{a}{p} \right) \equiv a^{\tfrac{p - 1}{2}} \pmod{p}

Kriteria ini berasal dari paper tahun 1748 karya Leonhard Euler.

## Bukti
### 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 untuk pembahasan lebih lanjut.

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

Diketahui bahwa a relatif prima dengan p, maka berdasarkan teorema kecil Fermat, berlaku
a^{p - 1} \equiv 1 \pmod{p}
yang dapat ditulis menjadi
\left( a^{\tfrac{p - 1}{2}} - 1 \right) \left( a^{\tfrac{p - 1}{2}} + 1 \right) \equiv 0 \pmod{p}
sebab p merupakan bilangan ganjil. Oleh karena himpunan bilangan bulat modulo p merupakan lapangan, maka salah satu dari kedua faktor tersebut harus kongruen dengan nol. Dengan kata lain, berlaku
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 a merupakan residu kuadratik modulo p, maka terdapat suatu k \in \mathbb{Z} sedemikian sehingga k^2 \equiv a \pmod{p}. Diketahui bahwa a relatif prima dengan p, maka k juga relatif prima dengan p. Akibatnya,
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 p akan membuat nilai dari faktor pertama menjadi nol. Berdasarkan teorema Lagrange, maka kekongruenan x^{\tfrac{p - 1}{2}} \equiv 1 \pmod{p} memiliki paling banyak \tfrac{p - 1}{2} penyelesaian, sehingga dapat disimpulkan bahwa \tfrac{p - 1}{2} kelas residu lainnya (yaitu nilai-nilai nonresidu kuadratik modulo p) harus membuat nilai dari faktor kedua menjadi nol. Inilah isi dari kriteria Euler.

### Bukti 2
Diambil sembarang bilangan prima ganjil p dan sembarang bilangan bulat a yang relatif prima dengan p. Akan ditinjau dua kasus berikut:
# Jika a merupakan residu kuadratik modulo p, maka berdasarkan definisi, terdapat suatu bilangan bulat n sedemikian sehingga n^2 \equiv a \pmod{p} Oleh karena a relatif prima dengan p, maka n juga relatif prima dengan p, sehingga berdasarkan teorema kecil Fermat, berlaku 1 \equiv n^{p - 1} = (n^2)^{\tfrac{p - 1}{2}} \equiv a^{\tfrac{p - 1}{2}} \pmod{p} 
# Perhatikan bahwa untuk setiap n \in \left\{ 1, \, 2, \, 3, \, \ldots, \, p - 1 \right\}, maka berlaku \operatorname{FPB} (n, \, p) = 1. Akibatnya, terdapat tepat satu nilai n' \in \left\{ 1, \, 2, \, 3, \, \ldots, \, p - 1 \right\} sedemikian sehingga n \cdot n' \equiv a \pmod{p} Diketahui bahwa a merupakan nonresidu kuadratik modulo p, maka nilai n' \neq n. Alhasil, setiap komponen dari darab 1 \cdot 2 \cdot 3 \cdot \ldots \cdot (p - 1) dapat disusun ulang menjadi \tfrac{p - 1}{2} pasangan sedemikian sehingga darab dari setiap pasangan akan kongruen dengan a dalam modulo p. Dengan menggunakan notasi faktorial serta teorema Wilson, maka 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 p dan sembarang bilangan bulat a yang relatif prima dengan p. Didefinisikan himpunan \mathbb{Z}_p sebagai \left\{ 1, \, 2, \, 3, \, \ldots, \, p - 1 \right\}. Perhatikan bahwa untuk setiap k \in \mathbb{Z}_p, maka berlaku \operatorname{FPB} (k, \, p) = 1. Akibatnya, terdapat tepat satu nilai k' \in \mathbb{Z}_p sedemikian sehingga k \cdot k' \equiv a \pmod{p}.
# Jika a merupakan nonresidu kuadratik, maka nilai k' \neq k untuk setiap nilai k \in \mathbb{Z}_p. Alhasil, semua elemen dari himpunan \mathbb{Z}_p dapat dikelompokkan menjadi \tfrac{p - 1}{2} pasangan sedemikian sehingga darab dari setiap pasangan akan kongruen dengan a dalam modulo p. Dengan menggunakan notasi faktorial serta simbol Legendre, maka (p - 1)! \equiv a^{\tfrac{p - 1}{2}} \equiv - \left( \dfrac{a}{p} \right) \cdot a^{\tfrac{p - 1}{2}} \pmod{p}
# Jika a merupakan residu kuadratik, maka berdasarkan definisi, terdapat suatu bilangan bulat n sedemikian sehingga n^2 \equiv a \pmod{p} Lebih lanjut, (p - n)^2 juga kongruen dengan a dalam modulo p, sebab (p - n)^2 \equiv p^2 - 2pn + n^2 \equiv n^2 \equiv a \pmod{p} Berdasarkan teorema Lagrange, maka kekongruenan x^2 \equiv a \pmod{p} memiliki paling banyak 2 penyelesaian pada himpunan \mathbb{Z}_p. Dengan kata lain, tidak ada nilai x \in \mathbb{Z}_p selain x = n dan x = p - n yang memenuhi kekongruenan tersebut. Akibatnya, p - 3 bilangan pada himpunan \mathbb{Z}_p \setminus \left\{ n, \, p - n \right\} dapat dikelompokkan menjadi \tfrac{p - 3}{2} pasangan sedemikian sehingga darab dari setiap pasangan akan kongruen dengan a dalam modulo p. Oleh karena n \cdot (p - n) \equiv -a \pmod{p}, maka dengan menggunakan notasi faktorial serta simbol Legendre, diperoleh (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 a yang relatif prima dengan p, maka berlaku
(p - 1)! \equiv - \left( \dfrac{a}{p} \right) \cdot a^{\tfrac{p - 1}{2}} \pmod{p}
Jika a = 1, maka jelas bahwa \left( \dfrac{a}{p} \right) = 1, sehingga didapatkan satu arah dari teorema Wilson, yaitu
(p - 1)! \equiv -1 \pmod{p}
Akibatnya, berlaku
\begin{align}
(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{align}
yang merupakan isi pernyataan dari kriteria Euler. Jika kedua ruas dari kekongruenan tersebut dikuadratkan, maka teorema kecil Fermat terbukti:
\begin{align}
\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{align}

## Contoh
### Mencari modulus jika diberikan nilai residu
*Bilangan prima <math>p</math> mana saja yang menjadikan 17 sebagai residu kuadratik?*

Dalam kasus ini, nilai p dapat diperiksa secara manual menggunakan kriteria Euler.
* Untuk p = 13, maka 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 17 \equiv 4 = 2^2 \pmod{13}.
* Untuk p = 11, maka 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
\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:
* 1^2 = 1 \pmod{17}
* 2^2 = 4 \pmod{17}
* 3^2 = 9 \pmod{17}
* 4^2 = 16 \pmod{17}
* 5^2 = 25 \equiv 8 \pmod{17}
* 6^2 = 36 \equiv 2 \pmod{17}
* 7^2 = 49 \equiv 15 \pmod{17}
* 8^2 = 64 \equiv 13 \pmod{17}
sehingga himpunan emua residu kuadratik modulo 17 ialah R_{17} = \left\{ 1, \, 2, \, 4, \, 8, \, 9, \, 13, \, 15, \, 16 \right\}. Perhatikan bahwa kuadrat dari 916 tidak perlu dihitung, sebab setiap bilangan mulai dari 9 sampai dengan 16 kongruen dengan negatif dari 1 sampai dengan 8 dalam modulo 17. Misalnya, 11 \equiv -6 \pmod{17}, sehingga 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, 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 14 \not \in R_{17})
* Untuk memeriksa apakah 15 merupakan residu kuadratik modulo 17, maka berdasarkan kriteria Euler, 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 15 \in R_{17})

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

* 
* 
* 
* 
* 
*