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