Teorema I

Jika y ¿ qx + r maka FPB(y, x) = FPB (x, r)

Bukti

Misalkan Misalkan FPB(y, x) = z berarti z½y dan z½x. Dari algoritma pembagian jika y = qx

+ r, karena z½y dan z½x maka z½r (Lihat teorema x ½ y dan x ½ (y + z) maka x ½ z ). z½x dan z½r

maka z = FP(x, r). Misalkan v = FP(x, r), akan ditujukkan v £ z. v = FP(x, r) berarti v½x dan

v½r. Karena y = qx + r, v½x dan v½r maka v½y (Lihat teorema x ½ y dan x ½ z maka x ½ (y + z) . v½y

dan v½x Akibatnya v = FP(y, x). Mengingat FPB(y, x) = z berarti v £ z. Ini berarti z = FPB(x,

r). Jadi FPB(y, x) = FPB(x, r) = z. (teorema terbukti)

Contoh :

Teorema II

(Alogiritma Uclides) jika x dan y bilangan-bilangan bulat positif, maka dengan menerapkan

algoritma pembagian berulang-ulang maka kita peroleh persamaan berikut :

y = qx + r dengan 0¿ r < x

x = q1r + r1 dengan 0¿ r1 < r

r = q2r1 + r2 dengan 0¿ r2 < r1

r1 = q3r2 + r3 dengan 0¿ r3 < r2

. .

. .

. .

rj-5 = qj-3rj-4 + rj-3 dengan 0¿ rj-3 < rj-4

rj-4 = qj-2rj-3 + rj-2 dengan 0¿ rj-2 < rj-3

rj-3 = qj-1rj-2 + rj-1 dengan 0¿ rj-1 < rj-2

rj-2 = qjrj-1 + rj dengan 0¿ rj < rj-1

rj-1 = qj+1rj

Maka FPB(y, x) = rj

Bukti

Rangkaian persamaan tersebut diperoleh dengan membagi y dengan x, x dengan r, r dengan

r1, r1 dengan r2, ..., rj dengan rj-1. Proses pembagian ini berhenti jika sisanya sama dengan 0

(lihat persamaan rj-1= qj+1rj sama dengan rj-1= qj+1rj + 0). Jadi penerapan teorema ini kita

tuliskan tanda ketidak samaan untuk sisa tanpa menggunakan sama dengan (=). Jadi kita

tuliskan 0¿ r < x sebagai ganti 0≤ r < x , sebab r ≠ 0. Rangkaian ini berhenti jika r ¿ 0 atau y

= qx ( lihat rj-1= qj+1rj ) dimana dalam kasus demikian FPB (y, x) = x.

Sekarang akan kita buktikan FPB (y, x) = rj. Perhatikan rangkaian diatas, menurut

sebelumnya Teorema I di atas. Maka baris pertama FPB(y, x) = FPB (x, r), baris ke-2

FPB(x,r) = FPB (r, r1), baris ke-3 FPB(r, r1 ) = FPB (r1, r2), baris ke-4 FPB (r1, r2) = FPB (r2,

r3), ..., FPB (rj-2, rj) = FPB (rj-1, rj) = rj . Maka FPB(y, x) = FPB (x, r) = FPB (r, r1) = FPB (r1, r2)

= FPB (r2, r3) =, ..., = FPB (rj-2, rj) = FPB (rj-1, rj ) = rj.

Jadi FPB (y, x) = rj (teorema terbukti)

Contoh :

Teorema III

Jika FPB(y, x) = rj maka ada bilangan bulat m dan n sedemikian hingga mx +ny =rj.

Bukti

dari rangkaian Teorema II di atas, jika r, r1, r2, r3, ..., rj-5, rj-4, rj-3, rj-2, rj-1, rj, dieliminasi

dimulai dari baris terakhir, yakni

FPB (y, x) = rj= rj-2−¿ qjrj-1 ...(1)

Dan kita subtitusikan rj-1= rj-3 −¿ qj-1rj-2 kedalam rj-1 pada persamaan (1) di atas, sehingga kita

peroleh:

rj = rj-2−¿ qjrj-1

= rj-2−¿ qj(rj-3 −¿ qj-1rj-2 )

= rj-2−¿ qjrj-3 −¿ qj qj-1rj-2

= (1 + qj qj-1) rj-2 −¿ qjrj-3 ...(2)

Dan kita subtitusikan rj-2 = rj-4 −¿ qj-2rj-3 ke dalam rj-2 pada persamaan (2) di atas, sehingga kita

peroleh:

rj = (1 + qj qj-1) rj-2 −¿ qjrj-3

= (1 + qj qj-1) (rj-4 −¿ qj-2rj-3) −¿ qjrj-3

= rj-4 −¿ qj-2rj-3 + qj qj-1 rj-4 −¿ qj qj-1 qj-2rj-3 −¿ qjrj-3

= ( 1 + qj qj-1) rj-4 + (−¿qj-2 −¿ qj qj-1 qj-2 −¿qj) rj-3 ...(3)

Dan rj-3¿ rj-5−¿ qj-3rj-4 kita subtitusikan ke rj-3 pada persamaan (4) di atas, sehinga kita peroleh:

rj = ( 1 + qj qj-1) rj-4 + (−¿qj-2 −¿ qj qj-1 qj-2 −¿qj) rj-3

= ( 1 + qj qj-1) rj-4 + (−¿qj-2 −¿ qj qj-1 qj-2 −¿qj) (rj-5−¿ qj-3rj-4)

= rj-4 + qj qj-1 rj-4 −¿ qj-2 rj-5 + qj-2 qj-3rj-4 −¿ qj qj-1 qj-2 rj-5 + qj qj-1 qj-2 qj-3rj-4

= (1+ qj qj-1 + qj-2 qj-3 + qj-1 qj-2 qj-3) rj-4 + (−¿ qj-2 −¿ qj qj-1 qj-2) rj-5

Apabila proses ini dilanjutkan secara berurutan hingga persamaan r = y −¿qx , maka akan

kita peroleh

mx + ny = rj.

dimana m dan n adalah bilangan-bilangan bulat. (toreme terbukti)

Untuk FPB(y, x) =1 maka ada bilangan bulat m,n sedemikian hingga mx + ny =1.

Fakta ini akan membuktikan relatif prima pada bilangan-bilangan bulat.

Bukti

Misalkan w = FPB(x, y), maka w½1. Karena w = FPB(x, y), maka w adalah bilangan bulat

positif. Jadi haruslah w =1. (teorema terbukti)

Teorema IV

Jika y½px dan FPB(x, y) = 1 maka y½p

Bukti

FPB(x, y) = 1 maka ada bilangan-bilangan bulat m dan n sedemikian hingga

1 = mx + ny (4)

Jika kedua ruas persamaan (4) dikalikan dengan p, maka kita peroleh

p = p(mx + ny) = m(px) + p(ny)

Karena y½px (yang diketahui) maka y½m(px) (Lihat teorema x ½ y maka x ½ p y ∀bil. Bulat p)

dan karena y½px maka y½p(ny). Karena y½m(px) dan y½p(ny) maka y½[m(px) + p(ny)] atau

y½p (Lihat teorema x ½ y dan x ½ z maka x ½ (y + z) ). (teorema terbukti)

Teorema V

Jika z½x dan w½x, FPB(z, w) = 1 maka zw½x.

Bukti

z½x berarti ada bilangan bulat p sedemikian hingga x = pz (definisi Habis bagi). w½x berarti

w½pz, karena FPB(z,w) = 1 maka w½p (Lihat torema IV di atas), misalkan p = kw, dengan k

sembarang bilangan bulat, maka

x = pz = (kw)z = (wz)k

x = (wz)k, untuk sebarang bilangan bulat k, berarti wz½x (definis habis bagi). (jadi teorema

terbukti)

Teorema VI

Jika FPB(x, z) = FPB(y, z) = 1 maka (xy, z) =1.

Bukti

Berdasarkan teorema III diatas terdapat bilangan-bilangan m0, n0, m1, n1 sedemikian hingga

1 = m0x + n0z = m1y + n1z

maka

(m0x)(m1y) = (1 - n0z)(1 - n1z)

= 1 – n2z (5)

dimana n2 = n0 + n1 - n0n1z. Dari persamaan (5) di atas diperoleh m0m1xy + n2z = 1, misalkan

d sembarang bilangan bulat sedemikian hingga d½xy dan d½z akibatnya d½(m0m1xy + n2z).

Karena m0m1xy + n2z = 1 maka d½1 ini hanya dipenuhi oleh d = 1. Karenanya FPB(xy, z) = 1.

(jadi teorema terbukti).