Teori Bilangan Kongruensi

teori bilangan kongruensi, kongruensi, pengertian kongruensi, sifat-sifat kongruensi, dalil-dalil kongruensi, teori konngruensi

BAB IV

KONGRUENSI LINEAR

4.1 Kongruensi Linear 

          Kongruensi mempunyai beberapa sifat yang sama dengan persamaan dalam Aljabar. Dalam Aljabar, masalah utamanya adalah menentukan akar-akar persamaan yang dinyatakan dalam bentuk f(x) = 0, f(x) adalah polinomial. Demikian pula halnya dengan kongruensi, permasalahannya adalah menentukan bilangan bulat x sehingga mememnuhi kongruensi

 f(x)  0 (mod m)

Definisi 4.1

Jika r₁, r₂, r₃, ... r_m adalah suatu sistem residu lengkap modulo m. Banyaknya selesaian dari kongruensi f(x)  0 (mod m) adalah banyaknya r_i sehingga f(r_i)  0 (mod m)

Contoh:

1.    f(x) = x³ + 5x – 4  0 (mod 7)

Jawab

Selesaiannya adalah x = 2, karena

f(2) = 2³ + 5(2) – 4 = 14  0 (mod 7)

Ditulis dengan x  2 (mod 7).

Untuk mendapatkan selesaian kongruensi di atas adalah dengan mensubstitusi x dari 0, 1, 2, 3, ...., (m-1).

2.    x³ –2x + 6   0 (mod 5)

Jawab

Selesaiannya adalah x = 1 dan x = 2, sehingga dinyatakan dengan

x  1 (mod 5) dan x  2 (mod 5).

3.    x² + 5  0 (mod 11)

Jawab

Tidak mempunyai selesaian, karena tidak ada nilai x yang memenuhi kongruensi tersebut.

          Bentuk kongruensi yang paling sederhana adalah kongruensi yang berderajat satu dan disebut dengan kongruensi linear. Jika dalam aljabar kita mengenal persamaan linear yang berbentuk ax = b, a 0, maka dalam teori bilangan dikenal kongruensi linear yang mempunyai bentuk ax  b (mod m).

 

Definisi 4.2

Kongruensi sederhana berderajat satu atau yang disebut kongruensi linear mempunyai bentuk umum ax  b (mod m), dengan a,b,m  Z , a 0, dan m > 0.

Kongruensi sederhana berderajat satu atau yang disebut kongruensi linear mempunyai bentuk umum ax  b (mod m), dengan a,b,m  Z , a 0, dan m > 0.

 

Teorema 4.1

Kongruensi linear ax  b (mod m), dengan a,b,m  Z , a 0, dan m > 0. dapat diselesaikan jika d = (a,m) membagi b. Pada kasus ini memiliki selesaian. Jika (a,m) = 1, maka kongruensi linear ax  b (mod m) hanya mempunyai satu selesaian.

Bukti.

Kongruensi linear ax  b (mod m) mempunyai selesaian, berarti m │ax – b.

Andaikan  d ┼b.

d = (a,b) → d │a   → d │ax.

d │ax. dan d ┼b  → d ┼ ax – b.

d= (a,m) → d │m.

d │m  dan d ┼b  → m ┼ ax – b.

m ┼ ax – b bertentangan dengan m │ax – b, Jadi d │b.

Diketahui d │b dan d = (a,m) → d │a   → d │m.

d │a  , d │m, dan d │b → , , dan   Z.

ax  b (mod m) → m │ax – b.

m │ax – b dan , ,  →│( - )

│ -  →    (mod ).

Misal selesaian kongruensi    (mod ) adalah x  x_o; x_o < , maka sebarang selesaiannya berbentuk x = x_o + k., k  Z, yaitu:

x = x_o + k., x = x_o + k., x = x_o + k., ..... , x = x_o + k..

dimana seluruhnya memenuhi kongruensi dan seluruhnya mempunyai d selesaian.

Jika (a,d) = 1, maka selesaiannya didapat x = x_o yang memenuhi kongruensi dan mempunyai satu selesaian.

Contoh:

1.    7x  3 (mod 12)

Jawab

Karena (7,12) = 1, atau 7 dan 12 relatif prima  dan 1 │ 3 maka 7x  3 (mod 12)

Hanya mempunyai 1 selesaian yaitu x  9 (mod 12)

2.    6x  9 (mod 15)

Jawab

Karena (6,15) = 3 atau 6 dan 15 tidak relatif prima dan 3│ 9, maka kongruensi di atas mempunyai 3 selesaian (tidak tunggal).

Selesaian kongruensi linear 6x  9 (mod 15) adalah

x  9 (mod 15),  x  9 (mod 15), dan x  14 (mod 15).

3.    12x  2 (mod 18)

Jawab

Karena (18,12) = 4 dan 4 ┼ 2, maka kongruensi 12x  2 (mod 18) tidak mempunyai selesaian.

4.    144x  216 (mod 360)

Jawab

Karena (144,360) = 72 dan 72│ 216, maka kongruensi 144x  216 (mod 360) mempunyai 72 selesaian.

Selesaian tersebut adalah x  4 (mod 360), x  14 (mod 360), .... , x  359 (mod 360).

5.    Bila kongruensi 144x  216 (mod 360) disederhanakan dengan menghilangkan faktor d, maka kongruensi menjadi 2x  3 (mod 5). Kongruensi 2x  3 (mod 5) hanya mempunyai satu selesaian yaitu x  4 (mod 5).

          Pada kongruensi ax  b (mod m) jika nilai a,b, dan m besar, akan memerlukan penyelesaian yang panjang, sehingga perlu disederhanakan penyelesaian tersebut.

ax  b (mod m) ↔ m│ (ax –b) ↔ (ax-b) = my, y  Z.

ax – b = my  ↔ my + b = ax ↔ my  - b (mod a) dan mempunyai selesaian y_o.

Sehingga dari bentuk my + b = ax dapat ditentukan bahwa my_o + b adalah kelipatan dari.

Atau dapat dinyatakan dalam bentuk:

my_o + b = ax ↔ x_o =

Contoh.

1.    Selesaikan kongruensi  7x  4 (mod 25)

Jawab

      7x    4 (mod 25)

      25y  -4 (mod 7)

      4y   -4 (mod 7)

        y    -1(mod 7)

        y_o = -1 sehingga x_o =  = -3

     Selesaian kongruensi linear di atas adalah

     x  -3 (mod 25)

     x  22 (mod 25)

2.    Selesaikan kongruensi  4x  3 (mod 49)

Jawab

      4x    3 (mod 49)

      49y  -3 (mod 4)

      4y   -3 (mod 4)

        y    -3 (mod 7)

        y_o = -3 sehingga x_o =  = -36

     Selesaian kongruensi linear di atas adalah

     x  -36 (mod 49)

     x  13 (mod 25)

Cara di atas dapat diperluas untuk menentukan selesaian kongruensi linear dengan

Menentukan y_o dengan mencari z_o

Menentukan w_o dengan mencari w_o

Menentukan v_o dengan mencari w_o, dan seterusnya.

Contoh

1.    Selesaikan kongruensi  82x  19 (mod 625)

Jawab

      82x    19 (mod 625)

      ----------------------------

      625y  -19 (mod 82)

        51y  -19 (mod 82)

     -----------------------------

        82z  19 (mod 51)

        31z  19 (mod 82)

     -----------------------------  

        51v  -19 (mod 31)

        20v  -19 (mod 31)

     -----------------------------

       31w  19 (mod 20)

        11w  19 (mod 20)

     -----------------------------

        20r  -19 (mod 11)

          9r  -19 (mod 11)

          9r   3 (mod 11)

     -----------------------------

      11s   -3 (mod 9)

        2s  -3 (mod 9)

     -----------------------------

       9t  3 (mod 2)

        t  3 (mod 2)

     -----------------------------

Jadi to = 3, sehingga:

s_o = (9t_o-3)/2 = (27-3)/2 = 12

r_o = (11s_o+3)/9 = (132+3)/9 = 15

w_o = (20r_o+19)/11 = (300+19)/11 = 29

v_o = (31w_o-19)/20 = (899-19)/20 = 44

z_o = (51v_o+19)/31 = (2244 +19)/31 = 73

y_o = (82z_o-19)/51 = (5986-19)/51 = 117

x_o = (625y_o+19)/82 = (73126+19)/82 = 892

Selesaian kongruensi di atas adalah

x  892 ( mod 625) atau x  267 ( mod 625)

 

Teorema 4.2  

Jika (a,m) = 1 maka kongruensi linear ax  b (mod m) mempunyai selesaian x = a^(m)-1b, dimana (m) adalah banyaknya residu didalam sistem residu modulo m tereduksi.

Bukti.

Menurut teorem Euler jika (a,m) = 1 maka a^(m)-1 = 1.

ax  b (mod m)

a. a^(m)-1 .x  b a^(m)-1 (mod m)

a ^(m)    b a^(m)-1 (mod m)

Karena a ^(m)  1 (mod m)  dan  a ^(m)  x  b a^(m)-1 (mod m)

Maka 1.x   b a^(m)-1 (mod m)

x   b a^(m)-1 (mod m)

x   a^(m)-1 b (mod m)

Contoh

1. Selesaikan  5x    3 (mod 13)

    Jawab

    Karena (5,13) = 1

    Maka kongruensi linear 5x    3 (mod 13) mempunyai selesaian

    x  3.5 ^{(13) –1} (mod 13)

         3.5 ^{12 –1} (mod 13)

            3.(5² )⁵.5 (mod 13)

            3.(-1)⁵  5 (mod 13), karena 5²  -1 (mod 13)

            11 (mod 13)

4.2 Kongruensi Simultan

Sering kita dituntut secara simultan untuk menentukan selesaian yang memenuhi sejumlah kongruensi. Hal ini berarti dari beberapa kongruensi linear yang akan ditentukan selesaiannya dan memenuhi masing-masing kongruensi linear pembentuknya.

Contoh

1.    Diberikan dua kongruensi (kongruensi simultan)

x  3 (mod 8)

x  7 (mod 10)

Karena x  3 (mod 8), maka  x = 3 + 8t (tZ).

Selanjutnya x = 3 + 8t  disubstitusikan ke x  7 (mod 10), maka diperoleh

3 + 8t  7 (mod 10) dan didapat

8t  7-3 (mod 10)

8t  4 (mod 10)

Karena (8,10) = 2 dan 2 │4 atau 2 │7-3, maka kongruensi 8t  4 (mod 10) mempunyai dua selesaian bilangan bulat modulo 10 yaitu

8t  4 (mod 10)

4t  2 (mod 5)

t  3 (mod 5)

Jadi t  3 (mod 5) atau  t  8 (mod 10)

Dari t  3 (mod 5)  atau t = 3 + 5r (rZ) dan t  8 (mod 10) atau x = 3 + 8t

Selanjutnya dapat dicari nilai x sebagai berikut:

x = 3 + 8t

   = 3 + 8(3+5r)

   = 3 + 24 + 40r

   = 27 + 40r atau x  27 (mod 40) atau x  27 (mod [8,10])

2.    Diberikan kongruensi simultan

x  15 (mod 51)

x  7 (mod 42)

Selesaian

Karena (51,42) = 3  dan 15/ 7 (mod 3) atau 3 ┼ 15 –7 , maka kongruensi simultan di atas tidak mempunyai selesaian.

Teorema 4.3

Kongruensi simultan

x  a (mod m)

x  b (mod n)

dapat diselesaikan jika

a  b (mod (m,n)) dana memiliki selesaian tunggal

x  x_o (mod [m,n])

Bukti

Diketahui

x  a (mod m)

x  b (mod n)

Kongruensi pertama  x  a (mod m) → x = a + mk, k Z.

Kongruensi kedua harus memenuhi a + mk  b (mod n) atau mk  b-a (mod n)

Menurut teorema sebelumnya mk  b-a (mod n) dapat diselesaikan jika

d │b-a, d = (m,n) atau dengan kata lain kondisi kongruensi a  b (mod (m,n)) harus dipenuhi.

d = (m,n) → d │ m dan d │m.

Jika  d│ m dan d │m maka , ,   Z.

, ,   Z dan mk  b-a (mod n) mengakibatkan

   ( mod )

Dari teorema sebelumnya jika d = (m,n) maka (, ) = 1

Jika (, ) = 1 dan    ( mod ), maka

   ( mod ) mempunyai 1 selesaian.

Misalkan selesaian yang dimaksud adalah k = k_o sehingga selesaian kongruensi adalah

k  k_o (mod ) atau k = k_o + r, r  Z.

Karena x = a = mk dan k = k_o + r, maka

x = a + mk

   = a + m (k_o + r)

   = ( a + m k_o + r)

  = ( a + m k_o ) + [m,n].r ; sebab [m,n](m,n) = m.n

  = x_o  + [m,n]r, sebab  x_o = ( a + m k_o )

  = x_o  (mod  [m,n]) 

4.3 Teorema Sisa China 

Dalil 4.4

Jika m₁, m₂, m₃, ... , m_r  Z+, dan (m_i,m_j) = 1 untuk i j, maka kongruensi simultan :

x  a₁ ( mod m₁)

x  a₂ ( mod m₂)

x  a₃ ( mod m₃)

.........................

.........................

x  a_r ( mod m_r)

Mempunyai selesaian persekutuan yang tunggal :

x    a_jb_j (mod [m₁,m₂,m₃,...,m_r]

Bukti

Misal m = m₁, m₂, m₃, ... , m_r

Karena  ( j = 1,2,3, ... , r) adalah bilangan bulat yang tidak memuat m_j, serta (m_i,m_j) =1 untuk i j maka  = 1.

Menurut dalil jika  = 1, maka kongruensi linear 1 (mod m_j) mempunyai 1 selesaian. Karena  masih memuat m_i, maka untuk i j

berlaku   0 (mod m_j).

Dengan memilih t =  a_jb_j , maka

t =  +  + ... +  + ... +

Dalam modulo m_i (i=1,2,3,..., r) t dapat dinyatakan dengan

t  (  +  + ... +  + ... + ) (mod m_i)

t    (mod m_i) + (mod m_i)  + ... +  (mod m_i) + ... + ) (mod m_i)

Karena   1 (mod m_j) dan untuk i j berlaku   0 (mod m_j) maka diperoleh:

  0 (mod mi) untuk i = 1,2,3,..., r. sehingga

  0 (mod mi) untuk i = 1,2,3,..., r.

Jadi t  0 (mod m_i) + 0 (mod m_i) + ...+ a_i (mod m_i) + ... + 0 (mod m_i)

      t  a_i (mod m_i).

Karena i = 1,2,3, ... , r maka

      t  a₁ (mod m₁)

      t  a₂ (mod m₂)

      t  a₃ (mod m₃)

     ......................

      t  a_r (mod m_r).

Hal ini berarti memenuhi semua kongruensi x  a_i (mod m_i). Dengan kata lain t merupakan selesaian persekutuan dari semua kongruensi linear simultan tersebut.

Contoh

1. Tentukan selesaian kongruensi simultan linear berikut:

x  5 (mod 8)

x  3 (mod 7)

x  4 (mod 9)

Jawab

Diketahui a₁ = 5, a₂ = 3, a₃ = 4 dan m₁ = 8, m₂ = 7, m₃ = 9.

Sehingga m = 8.7.9 = 504

(m₁,m₂) = 1, (m₁,m₃) = 1, (m₂,m₃) = 1.

Jadi kongruensi linear simultan memenuhi syarat untuk diselesaikan dengan teorema sisa China

  1 (mod m₁)   b₁  1 (mod 8)

                                   67 b₁  1 (mod 8)

                                        b₁  7

Dengan cara yang sama diperoleh b₂ = 4 dan b₃ = 5 

Jadi x =   a_jb_j

      x = 63.7.5 + 72.4.3 + 56.5.4

         = 4186

     x  4186 (mod [8.7.9])

     x   157 (mod 504)

2. Tentukan selesaian kongruensi

    19x  1 (mod 140)

Jawab

Karena 140 = 4.5.7 , maka kongruensi dapat dipilah menjadi kongruensi   simultan yaitu

19x  1 (mod 4)

19x  1 (mod 5)

19x  1 (mod 7)

Selanjutnya dapat disederhanakan menjadi

    x   3 (mod 4)

    x   4 (mod 5)

    x   3 (mod 7)

Dengan cara seperti contoh 1 di atas diperoleh

x = 899

x  899 (mod 140)

x  59 (mod 140)

Soal-soal

1.    Tentukan selesaian kongruensi linear di bawah ini

a.    3x       2 (mod 5)

b.    7x       4 (mod 25)

c.    12x     2 (mod 8)

d.    6x       9 (mod 15)

e.    36x     8 (mod 102)

f.     8x       12 (mod 20)

g.    144x         216 (mod 360)

2.    Tentukan selesaian kongruensi simultan berikut ini.

a.    12 x     3 (mod 15)

      10 x    14 (mod 8)

b.     x         5 (mod 11)

      x         3 (mod 23)

3. Selesaiakan kongruensi linear dengan metode my_o + b = ax

     ↔ x_o = :

a.    353x      19 ( mod 400)

b.    49x      5000 ( mod 999)

c.    589x     209 ( mod 817)

4. Selesaikan kongruensi linear simulat berikut dengan teorema sisa China.

a.  x  1 (mod 3)

    x   1 (mod 5)

    x   1 (mod 7)

b.    x  2 (mod 3)

    x   3 (mod 5)

    x   5 (mod 2) 

c.    x  1 (mod 4)

    x   0 (mod 3)

    x   5 (mod 7) 

d.    x  1 (mod 3)

    x   2 (mod 4)

    x   3 (mod 5) 

e. 23x  17 (mod 180)