Page 71 - Buku Siap OSN Matematika SMP 2015(1)

Teori Bilangan

KONGRUEN

Misalkan a, b bilangan bulat dan m suatu bilangan bulat positif. Kita katakan
a kongruen dengan b modulo m jika m membagi a – b. ditulis dengan a  b

mod m. Jika m tidak membagi a – b, maka kita tulis a  b mod m. Hubungan
a  b untuk bilangan bulat a dan b mempunyai banyak himpunan yang sama
dengan hubungan a  b.

Sifat. Untuk bilangan bulat a, b, c dan bilangan bulat positif m berlaku:

1. a  b mod m;

2. Jika a  b mod m, maka b  a mod m;

3. Jika a  b mod m dan b  c mod m, maka a  c mod m;
4. Jika a  b mod m untuk 1  i  n, maka a  a   a  b  b   b
i i 1 2 n 1 2 n
mod m;

5. Jika a + b  c mod m, maka a  c – b mod m;

6. Jika a  b mod m, maka a + c  b + c mod m;
7. Jika a  b mod m , maka a a  a  b b  b mod m;
i i 1 2 n 1 2 n
8. Jika a  b mod m, maka ac  bc mod m;

n
n
9. Jika a  b mod m, maka a  b mod m;
10. Jika a  b mod m dan f(x) adalah suku banyak dengan koefisien bilangan
bulat, maka f(a)  f(b) mod m;

Contoh

13
Jika 2 dibagi dengan 13, maka akan memberikan sisa samadengan ...
Jawab:
13
2 = 8192  2 (mod 13)
13
Jadi, 2 dibagi dengan 13 memberikan sisa 2.

62 Wahyu