Maintenance script: Presentation V4: sitasi, referensi, Math, Wikimedia Commons, dan atribusi

2026-08-25T13:57:03Z

Presentation V4: sitasi, referensi, Math, Wikimedia Commons, dan atribusi

← Revisi sebelumnya		Revisi per 25 Agustus 2026 13.57
Baris 1:		Baris 1:
	Dalam [[teori bilangan]], '''kriteria Euler''' adalah rumus untuk menentukan apakah suatu [[bilangan bulat]] merupakan [[residu kuadratik]] [[aritmetika modular\|modulo]] suatu [[bilangan prima]]. Lebih tepatnya,		Dalam [[teori bilangan]], '''kriteria Euler'''<ref>[https://pasti.kemendikdasmen.go.id/istilah_listdet.php?id=46813&char=E&page=105 kriteria Euler konjektur kuadrat]. ''Pasti (Padanan Istilah)''. Badan Pengembangan dan Pembinaan Bahasa.</ref> adalah rumus untuk menentukan apakah suatu [[bilangan bulat]] merupakan [[residu kuadratik]] [[aritmetika modular\|modulo]] suatu [[bilangan prima]]. Lebih tepatnya,

	\equiv \begin{cases}		\equiv \begin{cases}
Baris 10:		Baris 10:
	<math display="block">\left( \dfrac{a}{p} \right) \equiv a^{\tfrac{p - 1}{2}} \pmod{p}</math>		<math display="block">\left( \dfrac{a}{p} \right) \equiv a^{\tfrac{p - 1}{2}} \pmod{p}</math>

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

	== Bukti ==		== Bukti ==
Baris 17:		Baris 17:

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


	Diketahui bahwa <math>a</math> relatif prima dengan <math>p</math>, maka berdasarkan [[teorema kecil Fermat]], berlaku		Diketahui bahwa <math>a</math> relatif prima dengan <math>p</math>, maka berdasarkan [[teorema kecil Fermat]], berlaku
Baris 93:		Baris 92:

	== Catatan ==		== Catatan ==


	== Referensi ==		== 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.		<references />

	*
	*
	*
	*
	*
	*



	== Sumber dan atribusi ==		== Sumber dan atribusi ==

	Konten artikel ini diadaptasi dari [https://id.wikipedia.org/w/index.php?title=Kriteria+Euler&oldid=28775661 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.		Konten artikel ini diadaptasi dari [https://id.wikipedia.org/w/index.php?title=Kriteria+Euler&oldid=28775661 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.

			<!-- WIKI_UNISSULA_PRESENTATION_V4 -->

Maintenance script: Impor teks terkontrol dari Wikipedia bahasa Indonesia; revisi 28775661; atribusi sumber disertakan.

2026-08-25T13:17:13Z

Impor teks terkontrol dari Wikipedia bahasa Indonesia; revisi 28775661; atribusi sumber disertakan.

Halaman baru

Dalam [[teori bilangan]], '''kriteria Euler''' adalah rumus untuk menentukan apakah suatu [[bilangan bulat]] merupakan [[residu kuadratik]] [[aritmetika modular|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:

<math display="block">\left( \dfrac{a}{p} \right) \equiv a^{\tfrac{p - 1}{2}} \pmod{p}</math>

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 (matematika)|lapangan]]. Lihat artikel [[grup perkalian bilangan bulat modulo n|grup perkalian bilangan bulat modulo ]] untuk pembahasan lebih lanjut.

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

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

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

=== Bukti 2 ===
Diambil sembarang bilangan prima ganjil <math>p</math> dan sembarang bilangan bulat <math>a</math> yang relatif prima dengan <math>p</math>. Akan ditinjau dua kasus berikut:
# Jika <math>a</math> merupakan residu kuadratik modulo <math>p</math>, maka berdasarkan definisi, terdapat suatu bilangan bulat <math>n</math> sedemikian sehingga <math display="block">n^2 \equiv a \pmod{p}</math> Oleh karena <math>a</math> relatif prima dengan <math>p</math>, maka <math>n</math> juga relatif prima dengan <math>p</math>, sehingga berdasarkan [[teorema kecil Fermat]], berlaku <math display="block">1 \equiv n^{p - 1} = (n^2)^{\tfrac{p - 1}{2}} \equiv a^{\tfrac{p - 1}{2}} \pmod{p} </math>
# Perhatikan bahwa untuk setiap <math>n \in \left\{ 1, \, 2, \, 3, \, \ldots, \, p - 1 \right\}</math>, maka berlaku <math>\operatorname{FPB} (n, \, p) = 1</math>. Akibatnya, terdapat tepat satu nilai <math>n' \in \left\{ 1, \, 2, \, 3, \, \ldots, \, p - 1 \right\}</math> sedemikian sehingga <math display="block">n \cdot n' \equiv a \pmod{p}</math> Diketahui bahwa <math>a</math> merupakan nonresidu kuadratik modulo <math>p</math>, maka nilai <math>n' \neq n</math>. Alhasil, setiap komponen dari [[darab]] <math display="block">1 \cdot 2 \cdot 3 \cdot \ldots \cdot (p - 1)</math> dapat disusun ulang menjadi <math>\tfrac{p - 1}{2}</math> pasangan sedemikian sehingga darab dari setiap pasangan akan kongruen dengan <math>a</math> dalam modulo <math>p</math>. Dengan menggunakan notasi [[faktorial]] serta [[teorema Wilson]], maka <math display="block">a^{\tfrac{p - 1}{2}} \equiv (p - 1)! \equiv -1 \pmod{p}</math>

=== Bukti 3 ===
Bukti ini merupakan modifikasi dari [[#Bukti 2|Bukti 2]], dan dapat digunakan untuk membuktikan [[teorema Wilson]], kriteria Euler, dan [[teorema kecil Fermat]] sekaligus.

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

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

Dalam kasus ini, nilai <math>p</math> dapat diperiksa secara manual menggunakan kriteria Euler.
* Untuk <math>p = 13</math>, maka <math display="block">17^{\tfrac{13 - 1}{2}} = 17^6 \equiv 4^6 = 64^2 \equiv (-1)^2 = 1 \pmod{13}</math> sehingga dapat disimpulkan bahwa 17 merupakan residu kuadratik modulo 13. Sebagai konfirmasi, perhatikan bahwa <math>17 \equiv 4 = 2^2 \pmod{13}</math>.
* Untuk <math>p = 11</math>, maka <math display="block">17^{\tfrac{11 - 1}{2}} = 17^5 \equiv 6^5 \equiv 3^2 \cdot 6 \equiv -1 \pmod{11}</math> sehingga dapat disimpulkan bahwa 17 merupakan nonresidu kuadratik modulo 11.

Jika proses pemeriksaan ini terus dilanjutkan, maka diperoleh
<math display="block">\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}</math>

=== 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:
* <math>1^2 = 1 \pmod{17}</math>
* <math>2^2 = 4 \pmod{17}</math>
* <math>3^2 = 9 \pmod{17}</math>
* <math>4^2 = 16 \pmod{17}</math>
* <math>5^2 = 25 \equiv 8 \pmod{17}</math>
* <math>6^2 = 36 \equiv 2 \pmod{17}</math>
* <math>7^2 = 49 \equiv 15 \pmod{17}</math>
* <math>8^2 = 64 \equiv 13 \pmod{17}</math>
sehingga himpunan emua residu kuadratik modulo 17 ialah <math>R_{17} = \left\{ 1, \, 2, \, 4, \, 8, \, 9, \, 13, \, 15, \, 16 \right\}</math>. 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, <math>11 \equiv -6 \pmod{17}</math>, sehingga <math>11^2 \equiv (-6)^2 = 36 \equiv 2 \pmod{17}</math>.

Kriteria Euler dapat digunakan untuk mencari atau memverifikasi residu kuadratik. Misalnya,
* Untuk memeriksa apakah 14 merupakan residu kuadratik modulo 17, maka berdasarkan kriteria Euler, <math display="block">14^{\tfrac{17 - 1}{2}} = 14^8 \equiv (-3)^8 = 81^2 \equiv (-4)^2 = 16 \equiv -1 \pmod{17}</math> sehingga dapat disimpulkan bahwa 14 merupakan nonresidu kuadratik (yang sesuai dengan hasil di atas, yaitu <math>14 \not \in R_{17}</math>)
* Untuk memeriksa apakah 15 merupakan residu kuadratik modulo 17, maka berdasarkan kriteria Euler, <math display="block">15^{\tfrac{17 - 1}{2}} = 15^8 \equiv (-2)^8 = 16^2 \equiv (-1)^2 = 1 \pmod{17}</math> sehingga dapat disimpulkan bahwa 15 merupakan residu kuadratik (yang sesuai dengan hasil di atas, yaitu <math>15 \in R_{17}</math>)

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

*
*
*
*
*
*

== Sumber dan atribusi ==

Konten artikel ini diadaptasi dari [https://id.wikipedia.org/w/index.php?title=Kriteria+Euler&oldid=28775661 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.

Kriteria Euler - Riwayat revisi

Maintenance script: Presentation V4: sitasi, referensi, Math, Wikimedia Commons, dan atribusi

Maintenance script: Impor teks terkontrol dari Wikipedia bahasa Indonesia; revisi 28775661; atribusi sumber disertakan.