Bilangan Saling Prima ( Alogaritma Euklides)

Diberikan bilangan bulat b dan c dengan c > 0. Jika kita terapkan Alogaritma pembagian berkali-kali maka diperoleh persamaan-persamaan ini.

$b=cq_1+r_1$                 $0<r_1<c$

$c=r_1q_2+r_2$             $0<r_2<r_1$

$r_1=r_2q_3+r_3$         $0<r_3<r_2$

…………….                      ………………

$r_{j-2}=r_{j-1}+r_j$       $0<r_j<r_{j-1}$

$r_{j-1}=r_jq_{j+1}$

PBT b dan c, yaitu (b,c), adalah $r_j$ yang merupakan sisa tak nol pada langah ke-j dalam proses pembagian di atas

Catatan:

Nilai-Nilai $x_0$ dan $y_0$ dalam persamaan (b,c) = $bx_0+cy_0$ dapat diperoleh dengan mengeliminasian r₁,r₂,…,$r_{j-1}$ dari urutan persamaan di atas.

 

Teorema 12

Jika g = (b,c), yaitu g adalah PBT (Pembagi Bersama Terbesar) b dan c, maka g memiliki ciri-ciri berikut ini:

a. g adalah bilangan bulat positif terkecil yang berbentuk bx + cy untuk x dan y bilangan-bilangan bulat

b. g adalah pembagi bersama positif untuk b dan c dan g terbagi oleh tiap pembagi bersama b dan c

 

Contoh :

Cara 1

1. Diberikan b = 921 dan c = 654

Jawab:

921 = (654)(1) + 267

654 = (267)(2) +120

267 = (120)(2) + 27

120 = (27)(4) + 12

27 = (12)(2) + 3

12 = (3)(4)

Jadi (921,654) = 3, atau PBT 921 dan 654 adalah 3. Menurut Teorema 12 tedahulu, jika (921,654) = 3 maka x₀ dan y₀ sehingga

3 = (921)x₀ + (654)y₀

3 = 27 – (12)(2)

   = 27 – (2)(120 - (4)(27))

   = (9)(27) – (2)(120)

   = (9)(267- (2)(120)) – (2)(120)

   = (9)(267) – (20)(654 – (2)(267))

   = (49)(921 – 654) – (20) (654)

Jadi 3 = (49)(921) – (69)(654)

Diperoleh x₀ = 49 dan y₀ = –69 untuk 3 = (921)x₀ + (654)y₀

Cara 2

3. Diberikan a = 84 dan b = 60

Jawab :

84 = 1.(60) + 24                                  24 = (84) + (-1).60

60 = 2.(24) + 12                                  12 = 60 + (-2).(24)

24 = 2.(12),                                           12 = (84,60)

Selanjutnya dikerjakan secara mundur untuk mendapatkan

12 = 60 + (-2).(24)

      = 60 + (-2). (84 + (-1).(60))

      = (–2).84 + (3).60

Jadi (84,60) = 12 = (-2).84 + (3).60

4. Diberikan a = 190 dan b = –72

190 = (-2)(-72) + 46                                   46 = 190 + 2.(-72)     

-72 = (-2).46 + 20                                        20 = –72 + 2.46

46 = (2).20 + 6                                             6 = 46 + (-2).20

20 = (3).6 + 2                                               2 = 20 + (-3).6

6 = 3.2,                                                          2 = (190, –72)

Selanjutnya dikerjakan secara mundur untuk mendapatkan

2 = 20 + (-3).6

   = 20 + (-3).(46 + (-2).20)

   = (-3).46 + 7.20

   = (-3).4 + 7.(-72 + 2.46)

  = 7.(-72) + 11.46

  = 7.(-72) + 11.(190 + 2.(-72))

  = (11). 190 + 29.(-72)

Jadi (190, –72) = 2 =  (11). 190 + 29.(-72).

 

 

Sumber : Nanang. 2010.Teori Bilangan. Garut : STKIP Garut

                      Didit. 2009. Diktat Kuliah Teori Bilangan (Revisi Terakhir). Salatiga : Universitas Kristen Satya Wacana.