Kekongruenan

 
Konsep dari kekongruenan digunakan untuk mempelajari lebih mendalam mengenai konsep dan sifat-sifat dari keterbagian bilangan bulat. Konsep dari kekongruenan dijelaskan pada definisi berikut.
Definisi  (Rosen, 1993: 120)
Misalkan n adalah bilangan bulat positif. Jika a dan b adalah bilangan bulat, a dikatakan kongruen dengan b modulo n jika n│(a-b), dalam hal ini ditulis a ≡ b mod n dan a dikatakan tidak kongruen dengan b modulo n jika n ł (a-b).
Ilustrasi dari definisi kekongruenan diberikan pada Contoh berikut.
Contoh 
33 ≡ 6 mod 9 karena 9│(33 - 6) = 9│27.
7 tidak kongruen dengan 2 mod 9 karena 9 ł (7 - 2) = 9 ł 5.

Sifat-sifat dari kekongruenan bilangan bulat akan dibahas pada Teorema 1, Teorema 2 dan Teorema 3 berikut.

Teorema 1 (Rosen, 1993: 120)
Jika a dan b adalah bilangan bulat, maka  jika dan hanya jika terdapat sebuah bilangan bulat k sedemikian sehingga a = b + km.
Bukti
Jika a ≡ b mod m maka m│(a-b) yang berarti terdapat bilangan bulat k dengan km = a – b, sehingga a = b + km. Sebaliknya, jika terdapat bilangan bulat k dengan a = b + km, maka km = a - b. Sehingga m│(a-b), akibatnya a ≡ b mod m.
Untuk lebih jelasnya mengenai Teorema 1 diberikan contoh berikut.
Contoh
33 ≡ 6 mod 9 karena terdapat k = 3 sedemikian sehingga 33 = 6 + (3)(9).

 Berikut ini diberikan suatu Lemma yang akan digunakan untuk membuktikan sifat kekongruenan selanjutnya.

Lemma  (Rosen, 1993: 91)
Jika a, b dan k adalah bilangan bulat positif dengan a│bk dan gcd(a,b) = 1 maka a│k.
Bukti
Karena gcd(a,b) = 1 maka terdapat x dan y sehingga ax + by = 1. Perkalian kedua sisi persamaan dengan c diperoleh akx + bky = k. Jika a│a dan a│bk maka menurut Teorema 2 (pada pembahasan keterbagian), a membagi akx + bky, karena akx + bky adalah kombinasi linear dari a dan bk. Sehingga, a│akx + bky = a│k.
Sebagai ilustrasi dari Lemma  diberikan Contoh berikut.
Contoh
Jika terdapat bilangan 3, 5 dan 6, maka  3│6 karena  dan gcd(3,5) = 1.

Teorema 2 (Rosen, 1993: 122)
Jika a, b, k dan n adalah bilangan bulat sedemikian sehingga n > 0, gcd(k, n) = l dan ak ≡ (bk) mod n, maka a ≡ b mod (n/l).
Bukti
Jika ak ≡ (bk) mod n, maka n ⎸(ak-bk) = n ⎸k(a-b). Sehingga, terdapat bilangan bulat m dengan k(a-b) = mn. Kemudian kedua ruas dibagi dengan l maka diperoleh (k/l) (a-b) = m(n/l). Karena gcd(n/l,k/l) = 1, menurut Lemma di atas maka
n /l ⎸(a-b) sehingga a ≡ b mod (n/l).
Sebagai ilustrasi dari Teorema 2 diberikan Contoh berikut.
Contoh 
Jika 50 ≡ 20 mod 15 dan gcd(10,15) = 5 maka 50/10 ≡ 20/10(mod 15/5) atau 5 ≡ 2 mod 3.

Teorema 3 (Rosen, 1993: 124)
Jika a, b, k, dan m adalah bilangan bulat positif sedemikian sehingga k > 0,m > 0, dan a ≡ b mod m, maka a^k ≡ b^k mod m.
Bukti
Karena a ≡ b mod m dan m  ⎸(a-b) maka,
a^k - b^k = (a - b) (a^k-1 + a^k-2b + … + ab^k-2 + b^k-1), sehingga (a – b) ⎸( a^k - b^k).
Sehingga  menurut Teorema 1 maka   m ⎸( a^k - b^k) . Jadi, a^k ≡ b^k mod m.
Untuk lebih jelasnya, diberikan Contoh  berikut.
Contoh
Jika 5 ≡ 2 mod 3 menurut Teorema 3 maka 5² ≡ 2² mod 3.

Jika a dan m bilangan bulat dan gcd (a, m) = 1 maka dapat ditemukan balikan (invers) dari a modulo m. Definisi dari modulo invers sebagai berikut,
Definisi  (Rosen, 1993: 155)
Diberikan suatu bilangan bulat a dengan gcd(a, m) = 1,  maka invers dari a modulo m adalah x sedemikian sehingga
ax ≡ b mod m.
Untuk lebih jelasnya, diberikan Contoh 2 berikut.
Contoh
gcd(3, 8) = 1, maka invers dari 3 mod 8 adalah 3 sedemikian sehingga (3)(3)≡ 1 mod 8 .