Perkongruenan Linier

1. Perkongruenan Linier dan Bentuk Umum

A. Apa itu perkongruenan?

Kalimat terbuka yang menggunakan relasi kekongruenan disebut Perkongruenan, misalnya:

3x  ≡ 4 (mod 5)

x⁴ + 3x − 3 ≡ 0 (mod 31)

Jika suatu perkongruenan, variabelnya berpangkat paling tinggi satu disebut perkongruenan linier.

B. Bentuk umum

Bentuk Umum perkongruenan linier adalah:

ax  ≡ b (mod m), dengan  a ≢ 0 (mod m)

2. Solusi dari Perkongruenan Linier

• Perhatikan bahwa :

ax  ≡ b (mod m) berarti bahwa  ax – b = km  atau  ax = b + km, untuk suatu bilangan bulat k

Jadi perkongruenan linier ax ≡ b (mod m) akan mempunyai solusi atau penyelesaian bila dan hanya bila ada bilangan-bilangan bulat x dan k yang memenuhi persamaan ax = b + km. Misalkan r memenuhi perkongruenan linier ax ≡ b (mod m), berarti ar ≡ b (mod m). Maka setiap bilangan bulat :

(r + m), (r + 2m), (r + 3m), …, (r − m), (r − 2m), (r − 3m), …

memenuhi perkongruenan itu, sebab a(r + km) ≡ ar ≡ b (mod m), untuk setiap bilangan bulat k.

• Di antara bilangan-bilangan bulat (r + km), dengan k = 1, 2, 3, 4, -1, -2, -3,… ada tepat satu dan hanya satu, katakan s dengan 0 ≤ s ≤ m, sebab suatu bilangan bulat pasti terletak di antara dua kelipatan m yang berturutan.

Jadi, jika r memenuhi perkongruenan ax  ≡ b (mod m) dan 

km ≤ r ≤ (k + 1)m, untuk suatu bilangan bulat k maka 0 ≤ (r – km) < m. Sehingga diperoleh,  s = r – km, untuk suatu bilangan bulat k.

Dengan kata lain, s adalah residu terkecil modulo m yang memenuhi perkongruenan ax  ≡ b (mod m) dan s disebut solusi (penyelesaian) dari perkongruenan itu.

Contoh:

Nilai-nilai x yang memenuhi 3x ≡ 4 (mod 5) adalah:

..., -12, -7, -2, 3, 8, 13, 18, ...

Solusi dari perkongruenan itu adalah 3 yaitu residu terkecil modulo 5 yang memenuhi perkongrueanan linier 3x  ≡ 4 (mod 5).

Persamaan ax = b, dengan a ≠ 0 hanya mempunyai satu solusi, tetapi pada perkongruenan linier ax  ≡ b (mod m) dapat mempunyai tepat satu solusi, banyak solusi bahkan bisa juga tidak mempunyai solusi.

Contoh:

2x  ≡ 4 (mod 7) mempunyai tepat satu solusi yaitu 2.

2x  ≡ 4 (mod 6) mempunyai dua solusi yaitu 2 dan 5.

2x ≡ 1 (mod 4) tidak mempunyai solusi sebab 4 ∤ (2x – 1), artinya tidak ada bilangan bulat x sedemikian sehingga 2x – 1 terbagi oleh 4.

3. Solvabilitas

A. Perkongruenan linier yang tidak memiliki solusi

Jika (a, m) ∤ b maka perkongruenan linier ax  ≡ b (mod m) tidak memiliki solusi.

Bukti :

Kontraposisi dari teorema ini adalah: jika ax  ≡ b (mod m) memiliki solusi maka (a, m) | b.

Misalkan r adalah solusi dari ax ≡ b (mod m) 

                                               ar ≡ b (mod m)

ar – b = km, untuk suatu bilangan bulat k

Kita tahu bahwa (a, m) | km

karena ar – b = km, maka (a, m) | (ar – b)

(a, m) | a dan (a, m) | (ar – b), maka (a, m) | b

Terbuktilah kontraposisi teorema tersebut. Dengan demikian jika (a, m) ∤ b maka perkongruenan linier ax ≡ b (mod m) tidak memiliki solusi. ∎

Contoh:

2x ≡ 1 (mod 4) tidak mempunyai solusi karena (2, 4) = 2 ∤ 1

B. Perkongruenan linier yang memiliki tepat satu solusi

Jika (a, m) = 1 maka perkongruenan linier ax ≡ b (mod m) memiliki tepat satu solusi.

Bukti:

(a, m) = 1 berarti perkongruenan linier ax ≡ b (mod m) tidak dapat disederhanakan

Misalkan r adalah solusi dari ax ≡ b (mod m) berarti r merupakan anggota himpunan residu terkecil modulo m.

Dikarenakan perkongruenan linier tersebut tidak dapat disederhanakan, maka nilai selain r yang memenuhinya bukanlah anggota himpunan residu terkecil modulo m. Sehingga r merupakan satu-satunya solusi dari perkongruenan linier tersebut.

Dkl ax ≡ b (mod m) memiliki tepat satu solusi. ∎

Contoh:

Selesaikan 14𝑥 ≡ 27(𝑚𝑜𝑑 31)

Jawab:

Perhatikan bhw (14, 31) = 1, maka perkongruenan linier tsb memiliki tepat satu solusi.

14𝑥 ≡ 27 (𝑚𝑜𝑑 31) 

14𝑥 ≡ 58 (𝑚𝑜𝑑 31), krn (14, 31) = 1 maka

7𝑥 ≡ 29 (𝑚𝑜𝑑 31) 

7𝑥 ≡ 91 (𝑚𝑜𝑑 31), krn (7, 31) = 1 maka

𝑥 ≡ 13 (𝑚𝑜𝑑 31) 

Jadi, solusi dari 14𝑥 ≡ 27 (𝑚𝑜𝑑 31) adalah 13.

C. Perkongruenan linier yang memiliki lebih dari satu solusi

Jika (a, m) = d dan d | b maka perkongruenan linier ax ≡ b (mod m) memiliki tepat d solusi dan d ≤ m.

Bukti:

(a, m) = d berarti d | a dan d | m

dan d | b maka perkongruenan linier ax ≡ b (mod m) bisa disederhanakan menjadi:

(a/d)x ≡ (b/d)(mod m/d) karena a/d, b/d, m/d merupakan bil bulat

misalkan s adalah solusi dari perkongruenan linier (a/d)x ≡ (b/d)(mod m/d)

maka solusi dari ax ≡ b (mod m) adalah s + k.m/d, agar termasuk solusi diharuskan 0 ≤ k < d

sehingga perkongruenan linier ax ≡ b (mod m) memiliki tepat d solusi.

dan dikarenakan d | m maka d ≤ m ∎

Contoh:

Perhatikan bhw (6, 33) = 3 dan 3 | 15, sehingga perkongruenan linier tersebut memiliki tepat tiga solusi

6𝑥 ≡ 15 (𝑚𝑜𝑑 33), karena (6, 33) = 3 dan 3 | 15 maka dapat disederhanakan:

2𝑥 ≡ 5 (𝑚𝑜𝑑 11)

2𝑥 ≡ 16 (𝑚𝑜𝑑 11), karena (2, 11) = 1 maka

𝑥 ≡ 8 (𝑚𝑜𝑑 11), atau 𝑥 = 8 + 11k untuk k = 0, 1, 2, ...

Untuk 𝑘 = 0 → 𝑥 = 8

Untuk 𝑘 = 1 → 𝑥 = 8 + 11 = 19

Untuk 𝑘 = 2 → 𝑥 = 8 + 22 = 30

Sehingga solusi dari 6x ≡ 15 (𝑚𝑜𝑑 33) adalah {8, 19, 30}

4. Invers Modulo m

Invers dari a modulo m, ditulis a^-1(mod m) adalah solusi dari perkongruenan linier ax ≡ 1 (mod m). Suatu bilangan bulat a memiliki invers modulo m jika dan hanya jika (a, m) = 1, sebagaimana pada teorema solvabilitas.

Contoh:

Tentukan 5^-1(mod 13).

Untuk menyelesaikan 5^-1(mod 13), berarti sama dengan menyelesaikan perkongruenan linier

5𝑥 ≡ 1 (𝑚𝑜𝑑 13)

5𝑥 ≡ 40 (𝑚𝑜𝑑 13), karena (5, 13) = 1 maka

𝑥 ≡ 8 (𝑚𝑜𝑑 13)

Sehingga 5^-1(mod 13) = 8.