Apa itu Kekongruenan? — Matematika

Definisi 29.4 Matematika Sekolah Menengah Atas · Bab 29 — Aritmetika

Misalkan $n \in \N^*$ . Dua bilangan bulat $a, b$ disebut kongruen modulo $n$ , ditulis $a \equiv b \pmod n$ , jika $n \mid (a - b)$ — setara dengan mengatakan bahwa $a$ dan $b$ bersisa sama pada pembagian Euklides oleh $n$ .

Baca dalam konteks →

Definisi 6.18 Matematika Universitas — Tahun 1 · Bab 6 — Aritmetika Bilangan Bulat

Untuk $n \in \N^*$ : $a \equiv b \pmod n$ bila $n \mid a - b$ . Ini relasi ekuivalensi yang serasi dengan penjumlahan dan perkalian: jika $a \equiv b$ dan $a' \equiv b'$ (modulo $n$ ), maka $a + a' \equiv b + b'$ , $aa' \equiv bb'$ , dan $a^k \equiv b^k$ untuk $k \in \N$ .

Contoh

Contoh 6.19 (Uji buang sembilan)

Keserasiannya dengan $+$ dan $\times$ adalah alat pemeriksa yang setua perniagaan. Karena $10 \equiv 1 \pmod 9$ , setiap bilangan bulat kongruen modulo $9$ dengan jumlah angkanya (dibuktikan pada Latihan 6.2). Untuk memeriksa klaim $1234 \times 567 = 699\,678$ : jumlah angkanya memberikan $1234 \equiv 1$ dan $567 \equiv 18 \equiv 0 \pmod 9$ , jadi hasil kalinya haruslah $\equiv 1 \times 0 = 0$ ; dan memang $6 + 9 + 9 + 6 + 7 + 8 = 45 \equiv 0$ . Pemeriksaannya lolos (dan hasil kalinya memang benar). Seandainya ada yang melaporkan $699\,478$ , jumlah angkanya $43 \equiv 7 \not\equiv 0$ akan menghukumnya seketika. Ujinya bersifat sepihak — ia menangkap sebuah kesalahan kecuali bila kesalahannya sendiri kelipatan $9$ — dan itu persis pelajaran pseudoprima pada Contoh 6.24 dalam wujud mini: pemeriksaan kekongruenan membantah, tetapi tidak mengesahkan.

Contoh 6.21 (Membalikkan $7$ modulo $26$ )

Karena $\gcd(7, 26) = 1$ , kelas $7$ terbalikkan modulo $26$ . Euclid yang diperluas:

26 = 3 \times 7 + 5, \qquad 7 = 1 \times 5 + 2, \qquad 5 = 2 \times 2 + 1 ,

lalu secara mundur:

1 = 5 - 2 \times 2 = 5 - 2(7 - 5) = 3 \times 5 - 2 \times 7 = 3(26 - 3 \times 7) - 2 \times 7 = 3 \times 26 - 11 \times 7 .

Jadi $7 \times (-11) \equiv 1 \pmod{26}$ , yakni $7^{-1} \equiv -11 \equiv 15 \pmod{26}$ ; periksa: $7 \times 15 = 105 = 4 \times 26 + 1$ . Dengan inversnya di tangan, sebarang kekongruenan $7x \equiv c \pmod{26}$ diselesaikan dalam satu perkalian: $x \equiv 15c$ . Pembalikan mekanis inilah kuda beban aritmetika modular — dan juga kuda beban protokol kunci publik yang disebut pada Catatan 6.27, yang di sana modulusnya beratus angka tetapi algoritmanya persis yang ini.

Contoh 6.22 (Ketika koefisiennya tak terbalikkan)

Selesaikan $12x \equiv 8 \pmod{20}$ . Di sini $\gcd(12, 20) = 4$ , jadi $12$ tak terbalikkan modulo $20$ — tetapi persamaannya tetap tertangani. Kekongruenan itu mengatakan $20 \mid 12x - 8$ ; dengan membagi seluruh hubungannya dengan $4$ (pembagi ketiga bahannya), ia setara dengan $5 \mid 3x - 2$ , yakni

3x \equiv 2 \pmod 5 .

Sekarang $\gcd(3, 5) = 1$ dan $3^{-1} \equiv 2 \pmod 5$ (karena $3 \times 2 = 6 \equiv 1$ ), jadi $x \equiv 4 \pmod 5$ : penyelesaiannya adalah $x \equiv 4, 9, 14, 19 \pmod{20}$ — empat kelas modulo $20$ , yang cocok dengan FPB-nya. (Seandainya ruas kanannya tak habis dibagi $4$ , katakanlah $12x \equiv 6 \pmod{20}$ , tak akan ada penyelesaian sama sekali: karena ruas kirinya selalu $\equiv 0 \pmod 4$ .) Bentuk umumnya: $ax \equiv b \pmod n$ terselesaikan jika dan hanya jika $\gcd(a, n) \mid b$ , dan lalu ia mempunyai tepat $\gcd(a, n)$ kelas penyelesaian — bagi semuanya dengan FPB-nya lalu balikkan.

Baca dalam konteks →

Contoh

Istilah terkait