persamaan diophantine - · pdf filepersamaan diophantine terdiri dari persamaan diophantine...

Download PERSAMAAN DIOPHANTINE -  · PDF filePersamaan Diophantine terdiri dari persamaan Diophantine Linier dan persamaan ... aljabar yang pertama kali. ... Contoh soal 7.1

If you can't read please download the document

Author: dangdang

Post on 06-Feb-2018

416 views

Category:

Documents


49 download

Embed Size (px)

TRANSCRIPT

  • http://muhammadalfaridzi.wordpress.com/2014/06/07/persamaan-diophantine/

    http://muhammadalfaridzi.wordpress.com/2014/06/07/persamaan-diophantine/ 1

    PERSAMAAN DIOPHANTINE

    A. Pendahuluan

    Persamaan Diophantine terdiri dari persamaan Diophantine Linier dan persamaan

    Diophantine non-Linier.persamaan ini pertama kali ditulis oleh Diophantus (250 M)

    didalam bukunya yang berjudul Aritmathica dan buku ini dikenal sebagai buku

    aljabar yang pertama kali.

    B. Persamaan Diophantine Linier

    Persamaan Diophantine yang paling sederhana adalah memuat dua variable,pada

    umumnya dinyatakan dengan ax + by = c

    Dengan a,b,c z

    Dalil.7.1

    Ditentukan a,b,c Z dan d = ( a,b)

    a. Jika ( a,b) / c maka persamaan ax + by = c tidak mempunyai penyelesaian .

    b. Jika ( a,b) / c maka persamaan ax + by = c mempunyai penyelesaian bulat yang

    tak hingga banyaknya,yaitu pasangan ( x,y) dengan :

    x = xo + (b/d )n dan y = yo ( a/d)n

    Dengan n Z dan (xo ,yo ) adalah suatu penyelesaian bulat

    Contoh soal 7.1

    Selesaikan persamaan-persamaan Diophantine berikut :

    a. 4x +5y = 10

    b. 9x +12y =21

    c. 4x + 6y = 7

  • http://muhammadalfaridzi.wordpress.com/2014/06/07/persamaan-diophantine/

    http://muhammadalfaridzi.wordpress.com/2014/06/07/persamaan-diophantine/ 2

    Jawab :

    a. (4,5 ) = 1 10 ,persamaan mempunyai penyelesaian .

    Sesuai dengan Dalil Algoritma Euclides, karena (4,5 ) = 1 maka tentu ada x1,y1

    Z sehingga 4 x1,+ 5 y1 = 1

    Karena 5 = 1.4 + 1 atau 4 (-1) + 5 ( 1) = 1, maka x1= -1 ,y1 = -1

    4 (-1) + 5 ( 1) = 1

    10 [ 4 (-1) + 5 ( 1)] = 10 .1

    4 (-10) + 5 ( 10) = 10 ( ingat 4x +5y = 10 )

    Jadi : xo = -10 dan ,yo = 10

    Penyelesaian Persamaan adalah

    x = -10 + 5k dan

    y = 10- 4k dengan k Z

    b. ( 9,12 ) = 3 10 ,persamaan mempunyai penyelesaian .

    Sesuai dengan Dalil Algoritma Euclides, karena (9,12 ) = 3 maka tentu ada x1,y1

    Z sehingga 9 x1,+ 12 y1 = 3

    Karena 12 = 1.9 + 3 atau 9 (-1) + 12 ( 1) = 3, maka x1= -1 ,y1 = -1

    9 (-1) + 12 ( 1) = 3

    7 [ 9 (-1) + 12 ( 1)] = 7 .3

    9 (-7) + 12 ( 7) = 21 ( ingat 9x +12y = 21 )

    Jadi : xo = -7 dan ,yo = 7

    Penyelesaian Persamaan adalah

    x = xo + (b/d )t

    = -7 + ( 12 /3 ) t

    = -7 + 4t , dengan t Z

    y = yo ( a/d)t

    = 7 (9 / 3)t

    = 7 -3t , dengan t Z

    c. ( 4,6 ) = 2 , 2 7 ,persamaan tak mempunyai penyelesaian .

  • http://muhammadalfaridzi.wordpress.com/2014/06/07/persamaan-diophantine/

    http://muhammadalfaridzi.wordpress.com/2014/06/07/persamaan-diophantine/ 3

    1. CARA REDUKSI

    Cara lain yang dapat digunakan untuk menyelesaikan persamaan Diophantine Linier adalah

    mereduksikoefisien ( bukan variabel ) melalui pembagian berulang ( serupa dengan

    pembagian Algoritma ) sehingga diperoleh bentuk tanpa pecahan .

    Contoh soal 7.2

    a. selesaikan 4x + 5y = 10 dengan cara reduksi .

    jawab :

    4x + 5y = 10 4x = 10 -5y

    4

    510 yx

    x = 4

    248 yy

    x = 4

    2

    4

    48 yy

    x = 4

    2)22(

    yy

    ambil t =4

    2 y atau 2-y = 4t atau y = 2 -4t dari y = 2- 4t diperoleh :

    x = 4

    2)22(

    yy

    = 2- (2 -4t) + 4

    )42(2 t

    = 4t + t

    = 5t

    Penyelesaian persamaan adalah :

    x = 0 +5t

    y = 2 - 4t

  • http://muhammadalfaridzi.wordpress.com/2014/06/07/persamaan-diophantine/

    http://muhammadalfaridzi.wordpress.com/2014/06/07/persamaan-diophantine/ 4

    jika dibandingkan dengan penyelesaian pada contoh didepan maka hasil yang diperoleh

    nampak berbeda,sebetulnya dua jawaban itu sama

    x = -10 + 5k

    = 5 (-2 + k )

    = 5t dengan t = -2 + k atau k = t + 2

    y = 10- 4k

    = 10 -4 ( t + 2 )

    =10 4t 8

    = 2 4t

    Contoh soal 7.3

    Selesaikan 3x + 8y = 11 dengan cara reduksi

    Jawab :

    3x + 8y = 11 3x = 11 -8y

    3

    811 yx

    x = 3

    2269 yy

    x = 3

    22

    3

    69 yy

    x = 3

    22)23(

    yy

    ambil t =3

    22 y atau 2-2y = 3t atau

    2

    32 ty

    2

    22 tty

    dari

    2)1(

    tty

    ut

    u 22

    t = 2u y = ( 1- 2u) 4

    = 1-3u

  • http://muhammadalfaridzi.wordpress.com/2014/06/07/persamaan-diophantine/

    http://muhammadalfaridzi.wordpress.com/2014/06/07/persamaan-diophantine/ 5

    x = 3-2y + t

    = 3- 2( 1-3u ) + 2u

    =1+8u

    Penyelesaian persamaan adalah :

    x = 1+8u dan y = 1- 3u

    Contoh 7.4

    selesaikan x + 2 y + 3 z = 1 dengan cara reduksi

    jawab :

    x + 2y + 3z = 1 2y = - x 3z + 1

    y = 2

    13 zx

    y = 2

    1

    zxz

    t =2

    1 zx

    2t = - x z + 1

    Z = -x 2t + 1

    u = x 2t + 1 x = - u + 2t +1

    z = x 2t + 1 z = u

    y = - z + t y = -u + t

    penyelesaian perrsamaan adalah :

    x = - u + 2t +1

    y = -u + t

    z = u

  • http://muhammadalfaridzi.wordpress.com/2014/06/07/persamaan-diophantine/

    http://muhammadalfaridzi.wordpress.com/2014/06/07/persamaan-diophantine/ 6

    sekedar pengecekan ,dengan mengambil beberapa pasangan nilai u dan t dapat diketahui

    nilai- nilai ( x + 2y + 3z ) sebagai berikut :

    u t x 2y 3z x + 2y + 3z

    1 1 -2 0 3 1

    2 1 -3 -2 6 1

    2 3 -7 2 6 1

    Dari tabel nilai diatas dapat diketahui bahwa beberapa triple ( x ,y,z) yang memenuhi

    persamaan adalah ( -2 ,0,3), (-3 ,-2 ,6) ,(-7,2,6)

    2.CARA KONGRUENSI

    Contoh soal :

    Selesaikan persamaan-persamaan Diophantine linier berikut dengan cara kongruensi

    a. 2x + 5y = 11

    b. 2x + 3y + 7z = 15

    c. 6x + 15y = 8

    d. 35x + 14y = 91

    Jawaban a)

    2x +5y = 11 5y = 11- 2x

    5y 11 (mod 2)

    y 1 (mod 2)

    y 1 (mod 2) y = 1 + 2t

    2x +5y = 11 2x = 11 5y

    2x = 11 5 ( 1 + 2t )

    2x = 11 -5 -10t

    x = 3 5t

  • http://muhammadalfaridzi.wordpress.com/2014/06/07/persamaan-diophantine/

    http://muhammadalfaridzi.wordpress.com/2014/06/07/persamaan-diophantine/ 7

    Penyelesaian kongruensi adalah

    x = 3 5t dan y = 1 + 2t

    sekedar pengecekan ,dengan mengambil beberapa pasangan nilai u dan t dapat

    diketahui nilai- nilai (2x + 5y) sebagai berikut :

    t x y 2x 5y 2x + 5y

    1 2 1 4 5 11

    2 -7 5 -14 25 11

    4 -17 9 -34 45 11

    Jawaban b)

    2x +3y + 7z = 15 3y + 7z = 15- 2x

    3y + 7z 15 (mod 2)

    y + z 1 (mod 2)

    y (1- z) (mod 2)

    Ambil z = t ,maka y (1- z) + 2u = (1- t) + 2u

    y = 2u t + 1

    2x +3y + 7z = 15 2x = 15 -3y 7z

    = 15 -6u + 3t -3 7t

    =-6u -4t + 12

    x = 3u -2t + 6

    Penyelesaian kongruensi adalah

    x = 3u -2t + 6 dan y = 2u t + 1

  • http://muhammadalfaridzi.wordpress.com/2014/06/07/persamaan-diophantine/

    http://muhammadalfaridzi.wordpress.com/2014/06/07/persamaan-dio