Senin, 18 Juni 2012

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

Tidak ada komentar:

Posting Komentar