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}$)

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.

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.