Page 76 - MODUL KSM TEST

TEOREMA

Diberikan bilangan bulat a, b yang tidak keduanya nol, maka terdapat bilangan bulat x
dan y sehingga
(a, b) = ax + by

Contoh :

Hitunglah (247,299) dan tentukan bilangan-bilangan bulat m dan n yang
memenuhi 247m + 299n = (247, 299)
Jawab :
299 = 247.1 + 52
247 = 52.4 + 39
52 = 39.1 + 13
39 = 13.3
Jadi (247, 299) = 13
Selanjutnya,
13 = 52 - 39.1
= 52 - (247 - 52.4)
= 52.5- 247
= (299 - 247).5 - 247
13 = 299.5 + 247(-6)
Jadi m = -6 dan n = 5

Tetapi nilai m dan n yang memenuhi 247m + 299n = 13 tidak tunggal. Sebab
247(-6 + 299t) + 299(5 - 247t), untuk setiap bilangan bulat t. Jadi m = -6 +
299t dan n = 5 - 247t, untuk setiap bilangan bulat t .

DEFINISI
Dua bilangan bulat a dan b dikatakan relatif prima jika (a, b) = 1.

TEOREMA
Bilangan a dan b yang tidak keduanya nol, relatif prima jika dan hanya jika terdapat
x, y sehingga
xa + yb = 1