Aplikasi Algoritma Euclid

Tentukan bilangan bulat x dan y yang memenuhi persamaan 

a.      3551x + 4399y = 53.

b.     129x + 48y = 4

Jawab :

Persamaan 3551x + 4399y = 53

4399   = 1 x 3551 + 848      (persamaan 1)

3551   = 4 x 848 + 159        (persamaan 2)

848     = 5 x 159 + 53          (persamaan 3)

Sehingga         53        = 848 – 5 x 159                                             (dari persamaan 3)

                                    = 848 – 5 x (3551 – 4 x 848)                      (dari persamaan 2)

                                    = 848 – 5 x 3551 + 20 x 848

                                    = 21 x 848 – 5 x 3551

                                    = 21 x (4399 – 1 x 3551) – 5 x 3551         (dari persamaan 1)

                                    = 21 x 4399 – 21 x 3551 – 5 x 3551

                                    = 21 x 4399 – 26 x 3551

Maka nilai x = 21 dan y = -26

Persamaan 129x + 48y = 4

            129     = 2 x 48 + 33

            48        = 1 x 33 + 15

            33        = 2 x 15 + 3

            15        = 5 x 3 + 0

Karena tidak terdapat bentuk yang memberikan sisa 4, maka persamaan tersebut tidak memiliki penyelesaian bilangan bulat