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}</math>}}

Kriteria Euler dapat dirumuskan menggunakan simbol Legendre sebagai berikut:

$$\left(\frac{a}{p}\right)\equiv a^{\frac{p-1}{2}}(\mathrm{mod}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 $\frac{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(\mathrm{mod}p)$$ yang dapat ditulis menjadi $$(a^{\frac{p-1}{2}}-1)(a^{\frac{p-1}{2}}+1)\equiv 0(\mathrm{mod}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^{\frac{p-1}{2}}\equiv 1(\mathrm{mod}p)\text{atau}{a}^{\frac{p-1}{2}}\equiv -1(\mathrm{mod}p)$$

Jika $a$ merupakan residu kuadratik modulo $p$, maka terdapat suatu $k\in \mathbb{Z}$ sedemikian sehingga $k^2\equiv a(\mathrm{mod}p)$. Diketahui bahwa $a$ relatif prima dengan $p$, maka $k$ juga relatif prima dengan $p$. Akibatnya, $$a^{\frac{p-1}{2}}\equiv (k^2{)}^{\frac{p-1}{2}}=k^{p-1}\equiv 1(\mathrm{mod}p)$$ Dengan kata lain, setiap residu kuadratik modulo $p$ akan membuat nilai dari faktor pertama menjadi nol. Berdasarkan teorema Lagrange, maka kekongruenan $x^{\frac{p-1}{2}}\equiv 1(\mathrm{mod}p)$ memiliki paling banyak $\frac{p-1}{2}$ penyelesaian, sehingga dapat disimpulkan bahwa $\frac{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:

1. Jika $a$ merupakan residu kuadratik modulo $p$, maka berdasarkan definisi, terdapat suatu bilangan bulat $n$ sedemikian sehingga $$n^2\equiv a(\mathrm{mod}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{)}^{\frac{p-1}{2}}\equiv a^{\frac{p-1}{2}}(\mathrm{mod}p)$$
2. Perhatikan bahwa untuk setiap $n\in \{1,2,3,\dots ,p-1\}$, maka berlaku $\mathrm{FPB}(n,p)=1$. Akibatnya, terdapat tepat satu nilai $n^{\prime }\in \{1,2,3,\dots ,p-1\}$ sedemikian sehingga $$n\cdot n^{\prime }\equiv a(\mathrm{mod}p)$$ Diketahui bahwa $a$ merupakan nonresidu kuadratik modulo $p$, maka nilai $n^{\prime }\ne n$. Alhasil, setiap komponen dari darab $$1\cdot 2\cdot 3\cdot \dots \cdot (p-1)$$ dapat disusun ulang menjadi $\frac{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^{\frac{p-1}{2}}\equiv (p-1)!\equiv -1(\mathrm{mod}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 $\{1,2,3,\dots ,p-1\}$. Perhatikan bahwa untuk setiap $k\in {\mathbb{Z}}_p$, maka berlaku $\mathrm{FPB}(k,p)=1$. Akibatnya, terdapat tepat satu nilai $k^{\prime }\in {\mathbb{Z}}_p$ sedemikian sehingga $k\cdot k^{\prime }\equiv a(\mathrm{mod}p)$.

1. Jika $a$ merupakan nonresidu kuadratik, maka nilai $k^{\prime }\ne k$ untuk setiap nilai $k\in {\mathbb{Z}}_p$. Alhasil, semua elemen dari himpunan ${\mathbb{Z}}_p$ dapat dikelompokkan menjadi $\frac{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^{\frac{p-1}{2}}\equiv -\left(\frac{a}{p}\right)\cdot a^{\frac{p-1}{2}}(\mathrm{mod}p)$$
2. Jika $a$ merupakan residu kuadratik, maka berdasarkan definisi, terdapat suatu bilangan bulat $n$ sedemikian sehingga $$n^2\equiv a(\mathrm{mod}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(\mathrm{mod}p)$$ Berdasarkan teorema Lagrange, maka kekongruenan $x^2\equiv a(\mathrm{mod}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 \{n,p-n\}$ dapat dikelompokkan menjadi $\frac{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(\mathrm{mod}p)$, maka dengan menggunakan notasi faktorial serta simbol Legendre, diperoleh $$(p-1)!\equiv -a\cdot a^{\frac{p-3}{2}}\equiv -\left(\frac{a}{p}\right)\cdot a^{\frac{p-1}{2}}(\mathrm{mod}p)$$

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

Contoh

Mencari modulus jika diberikan nilai residu

Bilangan prima $p$ 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^{\frac{13-1}{2}}=17^6\equiv 4^6=64^2\equiv (-1{)}^2=1(\mathrm{mod}13)$$ sehingga dapat disimpulkan bahwa 17 merupakan residu kuadratik modulo 13. Sebagai konfirmasi, perhatikan bahwa $17\equiv 4=2^2(\mathrm{mod}13)$.
• Untuk $p=11$, maka $$17^{\frac{11-1}{2}}=17^5\equiv 6^5\equiv 3^2\cdot 6\equiv -1(\mathrm{mod}11)$$ sehingga dapat disimpulkan bahwa 17 merupakan nonresidu kuadratik modulo 11.

Jika proses pemeriksaan ini terus dilanjutkan, maka diperoleh $$\left(\frac{17}{p}\right)=\{\begin{array}{cc}1(\mathrm{mod}p)& \text{untuk}p\in \{13,19,43,\dots \}\\ -1(\mathrm{mod}p)& \text{untuk}p\in \{3,5,7,11,23,\dots \}\end{array}$$

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(\mathrm{mod}17)$
• $2^2=4(\mathrm{mod}17)$
• $3^2=9(\mathrm{mod}17)$
• $4^2=16(\mathrm{mod}17)$
• $5^2=25\equiv 8(\mathrm{mod}17)$
• $6^2=36\equiv 2(\mathrm{mod}17)$
• $7^2=49\equiv 15(\mathrm{mod}17)$
• $8^2=64\equiv 13(\mathrm{mod}17)$

sehingga himpunan emua residu kuadratik modulo 17 ialah $R_{17}=\{1,2,4,8,9,13,15,16\}$. 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(\mathrm{mod}17)$, sehingga $11^2\equiv (-6{)}^2=36\equiv 2(\mathrm{mod}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^{\frac{17-1}{2}}=14^8\equiv (-3{)}^8=81^2\equiv (-4{)}^2=16\equiv -1(\mathrm{mod}17)$$ sehingga dapat disimpulkan bahwa 14 merupakan nonresidu kuadratik (yang sesuai dengan hasil di atas, yaitu $14\in ̸R_{17}$)
• Untuk memeriksa apakah 15 merupakan residu kuadratik modulo 17, maka berdasarkan kriteria Euler, $$15^{\frac{17-1}{2}}=15^8\equiv (-2{)}^8=16^2\equiv (-1{)}^2=1(\mathrm{mod}17)$$ sehingga dapat disimpulkan bahwa 15 merupakan residu kuadratik (yang sesuai dengan hasil di atas, yaitu $15\in R_{17}$)

Sumber dan atribusi

Konten artikel ini diadaptasi dari Wikipedia bahasa Indonesia, revisi 28775661 (2026-01-03T18:14:56Z), yang tersedia berdasarkan lisensi Creative Commons Atribusi-BerbagiSerupa (CC BY-SA). Mohon gunakan konten ini secara bijak serta sesuai dengan ketentuan lisensi yang berlaku.