Aritmetika modular: Perbedaan antara revisi

[[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''}}).

 

 

:<math>a \equiv b \pmod n.</math>

 

== Sifat ==

* 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''}}.

* Jika {{math|''a x'' ≡ ''b'' (mod ''n'')}} dan {{math | '' a ''}} koprima dengan {{math | '' n ''}}, maka solusi untuk kongruensi linear ini diberikan oleh {{math|''x'' ≡ ''a''^–1''b'' (mod ''n'')}}

 

 

Secara khusus, jika {{math | '' p ''}} adalah bilangan prima, maka {{math | '' a ''}} coprima dengan {{math | '' p ''}} untuk {{math | '' a ''}} sehingga {{math|0 < ''a'' < ''p''}}; sehingga invers perkalian ada untuk semua {{math | '' a ''}} yang tidak kongruen dengan nol modulo {{math | '' p ''}}.

* [[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 koprima {{math | '' m ''}}, {{math | ' 'n' '}}, maka {{math|''x'' (mod ''mn'')}} seperti {{math|''x'' ≡ ''a'' (mod ''m'')}} dan {{math|''x'' ≡ ''b'' (mod ''n'')}}. Faktanya, {{math|''x'' ≡ ''b m''_''n''^–1 ''m'' + ''a n''_''m''^–1 ''n'' (mod ''mn'')}} dimana {{math|''m''_''n''⁻¹}} adalah kebalikan dari {{math | '' m ''}} modulo {{math | '' n ''}} dan {{math|''n''_''m''⁻¹}} adalah kebalikan dari {{math | '' n ''}} modulo {{math | '' m ''}}.

* [[Akar primitif modulo n]]: Bilangan {{math | '' g ''}} adalah akar primitif modulo {{math | '' n ''}}, untuk bilangan bulat {{math | '' a '' }} koprima dengan {{math | '' n ''}}, bilangan bulat {{math | '' k ''}} adalah {{math|''g''^''k'' ≡ ''a'' (mod ''n'')}}. Sebuah root modulo {{math | '' n ''}} ada jika dan hanya jika {{math | '' n ''}} sama dengan {{math|2, 4, ''p''^''k''}} atau {{math| 2''p''^''k''}}, dengan {{math | '' p ''}} adalah bilangan prima ganjil dan {{math | '' k ''}} adalah bilangan bulat positif. Jika aka4 modulo {{math | '' n ''}} primitif ada, maka persis ada {{math|''φ''(''φ''(''n''))}} akar primitif, di mana {{math | '' φ ''}} adalah fungsi total Euler.

* [[Residu kuadrat]]: Bilangan bulat {{math | '' a ''}} adalah modulo residu kuadrat {{math | '' n ''}}, jika terdapat bilangan bulat {{math | '' x ''}} seperti yang {{math|''x''² ≡ ''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

=== Sistem residu berkurang ===

{{Main|Mengurangi sistem residu}}

 

== Bilangan bulat modulo '' n '' ==

 

Himpunan ditentukan untuk '' n ''> 0 sebagai:

:<math>\mathbb{Z}/n\mathbb{Z} = \left\{ \overline{a}_n \mid a \in \mathbb{Z}\right\} = \left\{ \overline{0}_n, \overline{1}_n, \overline{2}_n,\ldots, \overline{n{-}1}_n \right\}.</math>

 

 

Kami mendefinisikan penjumlahan, pengurangan, dan perkalian di <math>\mathbb{Z}/n\mathbb{Z}</math> dengan aturan berikut:

seperti dalam aritmatika untuk sistem 24 jam.

 

 

== Aplikasi ==

 

Aplikasi yang sangat praktis adalah menghitung checksum dalam pengenal bilangan deret. Misalnya, [[Nomor Buku Standar Internasional]] (ISBN) menggunakan aritmatika modulo 11 (untuk 10 digit ISBN) atau modulo 10 (untuk ISBN 13 digit) untuk deteksi kesalahan. Demikian juga, [[Nomor Rekening Bank Internasional]] (IBAN), misalnya, menggunakan aritmatika modulo 97 untuk melihat kesalahan input pengguna di nomor rekening bank. Dalam kimia, digit terakhir dari [[nomor registrasi CAS]] (nomor pengenal unik untuk setiap senyawa kimia) adalah [[digit pemeriksa]], yang dihitung dengan mengambil digit terakhir dari dua bagian pertama [[Nomor CAS]] dikalikan 1, digit sebelumnya dikalikan 2, digit sebelumnya dikali 3 dll., menjumlahkan semua ini dan menghitung.

 

 

Dalam aljabar komputer, aritmatika modular biasanya digunakan untuk membatasi ukuran koefisien integer dalam penghitungan dan data menengah. Digunakan dalam [[faktorisasi polinomial]], masalah di mana semua algoritma efisien yang diketahui menggunakan aritmatika modular. Digunakan oleh implementasi yang paling efisien dari algoritma [[pembagi persekutuan terbesar polinomial]], eksak [[aljabar linear]] dan [[basis Gröbner]] di atas bilangan bulat dan bilangan rasional. Seperti yang diposting di [[Fidonet]] pada tahun 1980-an dan diarsipkan di [[Rosetta Code]], aritmatika modular digunakan untuk menyangkal [[konjektur jumlah pangkat Euler]] pada [[Sinclair QL]] [[mikrokomputer]] menggunakan hanya seperempat dari presisi integer yang digunakan oleh [[CDC 6600]] [[superkomputer]] untuk membantahnya dua dekade sebelumnya melalui [[pencarian brute force]].<ref>{{Cite web|title=Euler's sum of powers conjecture|url=https://rosettacode.org/wiki/Euler%27s_sum_of_powers_conjecture#QL_SuperBASIC|access-date=2020-11-11|website=rosettacode.org|language=en}}</ref>

</syntaxhighlight>

 

 

<syntaxhighlight lang="c">

** [[Grup perkalian bilangan bulat modulo n]]

* Teorema penting lainnya yang berkaitan dengan aritmatika modular:

** [[Teorema sisa Cina]]

** [[Teorema Euler]]

** [[Teorema kecil Fermat]] (kasus khusus dari teorema Euler)

** [[Lemma Thue]]

{{div col end}}

{{Teori bilangan}}