Aritmetika modular: Perbedaan antara revisi
Konten dihapus Konten ditambahkan
Tidak ada ringkasan suntingan Tag: Suntingan perangkat seluler Suntingan peramban seluler Suntingan seluler lanjutan |
k mengubah kata "coprime" menjadi "koprima", dan "relasi ekuivalen" menjadi "relasi ekuivalensi". Juga memberikan paranala dalam menuju artikel-artikel tersebut. |
||
Baris 11:
[[Bilangan bulat]] {{math|''n'' > 1}}, disebut '' 'modulus' '', dua bilangan bulat dikatakan '''kongruen''' modulo {{mvar | n}}, jika {{mvar | n}} adalah [[pembagian]] dari perbedaannya (yaitu, jika ada bilangan bulat {{math | '' k ''}} sehingga {{math|1=''a'' − ''b'' = ''kn''}}).
Modulo kongruensi {{mvar | n}} adalah [[relasi
:<math>a \equiv b \pmod n.</math>
Baris 42:
== Sifat ==
Relasi kesesuaian memenuhi semua kondisi dari [[relasi ekuivalen|relasi ekuivalensi]]:
* Refleksivitas: {{math|''a'' ≡ ''a'' (mod ''n'')}}
* Simetri: {{math|''a'' ≡ ''b'' (mod ''n'')}} jika {{math|''b'' ≡ ''a'' (mod ''n'')}} untuk {{math|''a''}}, {{math|''b''}}, dan {{math|''n''}}.
Baris 57:
Jika {{math|''a'' ≡ ''b'' (mod ''n'')}}, maka umumnya {{math|''k<sup>a</sup>'' ≡ ''k<sup>b</sup>'' (mod ''n'')}}. Namun, hal berikut ini benar:
* Jika {{math|''c'' ≡ ''d'' (mod ''φ''(''n'')),}} dengan {{math | '' φ ''}} adalah [[fungsi total Euler]], lalu asalkan {{math | '' a ''}} [[
Untuk pembatalan istilah umum, kami memiliki aturan berikut:
* Jika {{math|''a'' + ''k'' ≡ ''b'' + ''k'' (mod ''n'')}}, dengan {{math | '' k ''}} adalah sembarang bilangan bulat, lalu {{math|''a'' ≡ ''b'' (mod ''n'')}}
* Jika {{math|''k a'' ≡ ''k b'' (mod ''n'')}} dan {{math | '' k ''}}
* Jika {{math|''k a'' ≡ ''k b'' (mod ''kn'')}}, maka {{math|''a'' ≡ ''b'' (mod ''n'')}}
Baris 77:
Beberapa properti lanjutan dari hubungan kesesuaian adalah sebagai berikut:
* [[Teorema kecil Fermat]]: Jika {{math | '' p ''}} adalah bilangan prima dan tidak membagi {{math | '' a ''}}, maka {{math|''a'' <sup>''p'' – 1</sup> ≡ 1 (mod ''p'')}}.
* [[Teorema Euler]]: Jika {{math | '' a ''}} dan {{math | '' n ''}}
* Konsekuensi sederhana dari teorema kecil Fermat adalah jika {{math | '' p ''}} adalah bilangan prima, maka {{math|''a''<sup>−1</sup> ≡ ''a'' <sup>''p'' − 2</sup> (mod ''p'')}} adalah kebalikan perkalian dari {{math|0 < ''a'' < ''p''}}. Lebih umum lagi, dari teorema Euler, jika {{math | '' a ''}} dan {{math | '' n ''}} adalah
* Konsekuensi sederhana lainnya adalah jika {{math|''a'' ≡ ''b'' (mod ''φ''(''n'')),}} dengan {{math | '' φ ''}} adalah fungsi total Euler, maka {{math|''k''<sup>''a''</sup> ≡ ''k''<sup>''b''</sup> (mod ''n'')}} asalkan {{math | '' k ''}} adalah [[coprime|koprima]] dengan {{math | '' n ''}}.
* [[Teorema Wilson]]: {{math|''p''}} is prime if and only if {{math|(''p'' − 1)! ≡ −1 (mod ''p'')}}.
* [[Teorema sisa Cina]]: Untuk {{math | '' a ''}}, {{math | '' b ''}}, dan
* [[Teorema Lagrange (teori bilangan) | Teorema Lagrange]]: Kesesuaian {{math|''f'' (''x'') ≡ 0 (mod ''p'')}}, dengan {{math | '' p ''}} adalah bilangan prima, dan {{math|''f'' (''x'') {{=}} ''a''<sub>0</sub> ''x''<sup>''n''</sup> + ... + ''a''<sub>''n''</sub>}} adalah [[polinomial]] dengan koefisien bilangan bulat {{math|''a''<sub>0</sub> ≠ 0 (mod ''p'')}}, memiliki akar {{math | '' n ''}}.
* [[Akar primitif modulo n]]: Bilangan {{math | '' g ''}} adalah akar primitif modulo {{math | '' n ''}}, untuk bilangan bulat {{math | '' a '' }}
* [[Residu kuadrat]]: Bilangan bulat {{math | '' a ''}} adalah modulo residu kuadrat {{math | '' n ''}}, jika terdapat bilangan bulat {{math | '' x ''}} seperti yang {{math|''x''<sup>2</sup> ≡ ''a'' (mod ''n'')}}. [[Kriteria Euler]] menegaskan bahwa, jika {{math | '' p ''}} adalah bilangan prima ganjil, dan {{mvar | a}} bukan kelipatan {{mvar | p}}, maka {{math | '' a ''}} adalah modulo residu kuadrat {{math | '' p ''}} jika dan hanya jika
::<math>a^{(p-1)/2} \equiv 1 \pmod p.</math>
== Kelas kongruensi {{Anchor|Residu | Kelas residu | Kelas kongruensi}} ==
Seperti relasi kesesuaian lainnya, kongruensi modulo {{math | '' n ''}} adalah [[relasi
== Sistem residu ==
| |||