Kriteria Euler

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

Kriteria Euler dapat dirumuskan menggunakan simbol Legendre sebagai berikut:

Kriteria ini berasal dari paper tahun 1748 karya Leonhard Euler.L Euler, Novi commentarii Academiae Scientiarum Imperialis Petropolitanae, 8, 1760-1, 74; Opusc Anal. 1, 1772, 121; Comm. Arith, 1, 274, 487

 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  dan sembarang bilangan bulat  yang relatif prima dengan . Pertama, akan dibuktikan bahwa terdapat  nilai residu kuadratik tak nol berbeda dalam himpunan bilangan bulat modulo .

Diketahui bahwa  relatif prima dengan , maka berdasarkan teorema kecil Fermat, berlaku

yang dapat ditulis menjadi

sebab  merupakan bilangan ganjil. Oleh karena himpunan bilangan bulat modulo  merupakan lapangan, maka salah satu dari kedua faktor tersebut harus kongruen dengan nol. Dengan kata lain, berlaku

Jika  merupakan residu kuadratik modulo , maka terdapat suatu  sedemikian sehingga . Diketahui bahwa  relatif prima dengan , maka  juga relatif prima dengan . Akibatnya,

Dengan kata lain, setiap residu kuadratik modulo  akan membuat nilai dari faktor pertama menjadi nol. Berdasarkan teorema Lagrange, maka kekongruenan  memiliki paling banyak  penyelesaian, sehingga dapat disimpulkan bahwa  kelas residu lainnya (yaitu nilai-nilai nonresidu kuadratik modulo ) harus membuat nilai dari faktor kedua menjadi nol. Inilah isi dari kriteria Euler.

 Bukti 2 
Diambil sembarang bilangan prima ganjil  dan sembarang bilangan bulat  yang relatif prima dengan . Akan ditinjau dua kasus berikut:
 Jika  merupakan residu kuadratik modulo , maka berdasarkan definisi, terdapat suatu bilangan bulat  sedemikian sehingga  Oleh karena  relatif prima dengan , maka  juga relatif prima dengan , sehingga berdasarkan teorema kecil Fermat, berlaku 
 Perhatikan bahwa untuk setiap , maka berlaku . Akibatnya, terdapat tepat satu nilai  sedemikian sehingga  Diketahui bahwa  merupakan nonresidu kuadratik modulo , maka nilai . Alhasil, setiap komponen dari darab  dapat disusun ulang menjadi  pasangan sedemikian sehingga darab dari setiap pasangan akan kongruen dengan  dalam modulo . Dengan menggunakan notasi faktorial serta teorema Wilson, maka 

 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  dan sembarang bilangan bulat  yang relatif prima dengan . Didefinisikan himpunan  sebagai . Perhatikan bahwa untuk setiap , maka berlaku . Akibatnya, terdapat tepat satu nilai  sedemikian sehingga .
 Jika  merupakan nonresidu kuadratik, maka nilai  untuk setiap nilai . Alhasil, semua elemen dari himpunan  dapat dikelompokkan menjadi  pasangan sedemikian sehingga darab dari setiap pasangan akan kongruen dengan  dalam modulo . Dengan menggunakan notasi faktorial serta simbol Legendre, maka 
 Jika  merupakan residu kuadratik, maka berdasarkan definisi, terdapat suatu bilangan bulat  sedemikian sehingga  Lebih lanjut,  juga kongruen dengan  dalam modulo , sebab  Berdasarkan teorema Lagrange, maka kekongruenan  memiliki paling banyak 2 penyelesaian pada himpunan . Dengan kata lain, tidak ada nilai  selain  dan  yang memenuhi kekongruenan tersebut. Akibatnya,  bilangan pada himpunan  dapat dikelompokkan menjadi  pasangan sedemikian sehingga darab dari setiap pasangan akan kongruen dengan  dalam modulo . Oleh karena , maka dengan menggunakan notasi faktorial serta simbol Legendre, diperoleh 
Berdasarkan kedua kasus di atas, maka untuk setiap nilai  yang relatif prima dengan , maka berlaku

Jika , maka jelas bahwa , sehingga didapatkan satu arah dari teorema Wilson, yaitu

Akibatnya, berlaku

yang merupakan isi pernyataan dari kriteria Euler. Jika kedua ruas dari kekongruenan tersebut dikuadratkan, maka teorema kecil Fermat terbukti:

 Contoh 
 Mencari modulus jika diberikan nilai residu 
Bilangan prima  mana saja yang menjadikan 17 sebagai residu kuadratik?

Dalam kasus ini, nilai  dapat diperiksa secara manual menggunakan kriteria Euler.
 Untuk , maka  sehingga dapat disimpulkan bahwa 17 merupakan residu kuadratik modulo 13. Sebagai konfirmasi, perhatikan bahwa .
 Untuk , maka  sehingga dapat disimpulkan bahwa 17 merupakan nonresidu kuadratik modulo 11.

Jika proses pemeriksaan ini terus dilanjutkan, maka diperoleh

 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:








sehingga himpunan emua residu kuadratik modulo 17 ialah . 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, , sehingga .

Kriteria Euler dapat digunakan untuk mencari atau memverifikasi residu kuadratik. Misalnya,
 Untuk memeriksa apakah 14 merupakan residu kuadratik modulo 17, maka berdasarkan kriteria Euler,  sehingga dapat disimpulkan bahwa 14 merupakan nonresidu kuadratik (yang sesuai dengan hasil di atas, yaitu )
 Untuk memeriksa apakah 15 merupakan residu kuadratik modulo 17, maka berdasarkan kriteria Euler,  sehingga dapat disimpulkan bahwa 15 merupakan residu kuadratik (yang sesuai dengan hasil di atas, yaitu )

 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.








Kategori:Artikel yang memuat pembuktian
Kategori:Aritmetika modular
Kategori:Residu kuadratik
Kategori:Kuadrat dalam teori bilangan
Kategori:Teorema mengenai bilangan prima