Menggunakan pembagian euclid, Lemma, cari KPK dari 441 567 693

Menggunakan pembagian euclid, Lemma, cari KPK dari 441 567 693

.Menurut Lemma Pembagian Euclid jika kita mempunyai dua bilangan bulat positif a dan b, maka terdapat bilangan bulat unik q dan r yang memenuhi syarat a = bq + r dimana 0 r < b. Itu berarti, membagi kedua bilangan bulat a dan b sisanya adalah nol.

Algoritma Euclidean untuk mencari HCF (A,B) adalah sebagai berikut:

Jika A=0 maka HCF (A,B)=B,

karena HCF (0,B)=B, dan kita bisa berhenti.

Jika B=0 maka HCF (A,B)=A,

karena HCF (A,0)=A, dan kita bisa berhenti.

Tulis A dalam bentuk sisa bagi (A=BQ+R)

Cari FCF (B,R) menggunakan Algoritma Euclidean karena HCF (A,B)=HCF(B,R)

Di sini, HCF dari 441 dan 567 dapat ditemukan sebagai berikut:-

567=441×1+126

441=126×3+63

126=63×2+0

Karena sisa adalah 0,

oleh karena itu, FPB dari (441.567) adalah =63

Sekarang KPK dari 63 dan 693 adalah 693 = 63 × 11 + 0

Oleh karena itu, KPK dari (63.693)=63

Jadi, FKH dari (441.567.693)=63.

10