Kekongruenan

Misalkan a dan b adalah suatu bilangan bulat. Jika m suatu bilangan bulat positif yang lebih besar dari 1, maka a dikatakan kongruen dengan b modulo m ( ditulis a ≡ b ( mod m) ) jika m membagi habis ( a – b ).

Atau a ≡ b ( mod m ) jika a dan b memberikan sisa yang sama bila dibagi oleh m.

CONTOH

1.  Buktikan bahwa ( am + b )ⁿ ≡ bⁿ ( mod m ). Bukti :

Akan dibuktikan ada k sedemikian sehingga (am + b )ⁿ  - bⁿ = km.

( am + b )ⁿ – bⁿ = ( am ) + n(am).b^n-1 + … + n(am) b^n-1 + bⁿ – bⁿ

=  { a(am)^n-1 + an(am)^n-2 + … + an(b)^n-1 } m = k m

Cara di atas dapat digunakan untuk menentukan sisa pembagian bilangan yang cukup besar.

2. Tentukan sisa jika 3¹⁹⁹⁰ jika dibagi 41.

Penyelesaian :

3¹⁹⁹⁰ ( mod 41 ) ≡ 3^{4 × 497 + 2} ( mod 41)

≡  (3⁴)⁴⁹⁷ × 3² ( mod 41)

≡  ( 2 × 41 – 1 )⁴⁹⁷ × 9 ( mod 41 )

≡  (-1)⁴⁹⁷ × 9 ( mod 41 )

≡  -9 ( mod 41 )

≡  ( 41 – 9 ) ( mod 41 )

≡  32 ( mod 41 )

Jadi sisa 3¹⁹⁹⁰ dibagi oleh 41 adalah 32.

3.  Tentukan angka terakhir dari 777³³³. Penyelesaian:

Mencari angka terakhir = menentukan sisa pembagian oleh 10.

777³³³ ≡ ( 77 × 10 + 7) ³³³ ( mod 10 )

≡   7³³³ ( mod 10 )

≡   7^{2 × 166+1} ( mod 10)

≡   (7²)¹⁶⁶ × 7 ( mod 10)

≡   9^{2 × 83} × 7 ( mod 10 )

≡   (81)⁸³ × 7 ( mod 10 )

≡   1⁸³ × 7 ( mod 10)

≡   7 ( mod 10), jadi angka terakhir dari 777³³³ adalah 7.