menentukan fpb dengan algoritma euclides

MENENTUKAN FPB DENGAN ALGORITMA EUCLIDES

Jika maka dengan menerapkan algoritma euclides, pembagian berkali-kali diperoleh :

Bba ,

n

nnn

nnnnnn

r

qrr

rrrqrr

rrrqrr

rrrqrb

brrbqa

b)FPB(a, maka

0 ,

...................

0

0,

0 ,

11

112

23,3321

12221

111

CONTOH :• Tentukan FPB(9800, 180)

9800= 180.54+80180 = 80.2+2080 = 20.4 FPB(9800, 180)= 20

Jika FPB(a,b)=d maka ada bilangan bulat x dan y sehingga ax+by=d

FPB(9800, 180)= 2020 = 180-80.220 = 180-(9800-180.54)220 = 180-9800.2+180.10820 = 180.109-9800.220 = 9800(-2)+180(109)

Jadi x=-2 dan y=109

KELIPATAN PERSEKUTUAN TERKECIL

TEOREMA :

Jika a dan b bilangan bulat positif maka KPK(a, b) = ),(

.

baFPB

ba

BUKTI :

Jika Bba, dengan FPB(a,b) = 1

maka KPK(a,b) = ba

menurut sifat FPB : FPB(a,b) = d→FPB(a:d, b:d) = 1

sehingga KPK d

b

d

a

d

b

d

a

,

2d

ab

KPK

d

bd

d

adba ,,

d

abd

abd

d

b

d

ad

2

,KPK

),(

.,KPK

baFPB

baba

CONTOH :

8820020

176400020

1809800180,9800KPK

LATIHAN :

Tentukan FPB, nilai x dan y serta KPK dari

pasangan bilangan berikut :

1. 10.587 dan 534

2. 1.587.645 dan 6.755

3. 12.345 dan 9.999

BILANGAN PRIMA DAN FAKTORISASI PRIMA

•Bilangan prima adalah suatu bilangan bulat p>1 yang tidak punya faktor positif selain 1 dan p.

•Bilangan bulat p>1 yang bukan merupakan bilangan prima disebut bilangan komposit.

•1 bukan bilangan prima dan bukan bilangan komposit (unit).