Materi Olimpiade SMP : Bab 5 Teori Bilangan [Basic] : Persamaan Kongruensi

Materi sebelumnya : Materi Olimpiade SMP : Bab 4 Teori Bilangan [Basic] : Pembagian Bersisa dan Kongruensi

Untuk lebih memahami materi ini, kita langsung saja membahas soal - soal yang berkaitan dengan persamaan kongruensi

Soal 1
Carila semua bilangan $x$ yang memenuhi persamaan $7 + x \equiv 4 \pmod{5}$

Solusi
Persamaan diatas equivalen dengan $x \equiv 4 - 7 \pmod{5} \equiv -3 \pmod{5} \equiv 2 \pmod{5}$

Soal 2
apakah persamaan berikut memiliki solusi ? Jika ya, cari solusinya
(a) $6x  \equiv 5 \pmod{3}$
(b) $5x \equiv 1 \pmod{7}$

Solusi
(a) Perhatikan bahwa ruas kanan yaitu $6x$ habis dibagi $3$, sedangkan ruas kiri yaitu $5$ tidak habis dibagi $3$. Akibatnya, kesamaan tidak akan pernah tercapai. Jadi, persamaan ini tidak meiliki solusi

(b) Perhatikan bahwa dengan metode trial and error

$5x \equiv 1 \pmod{7}$      ($1$ tidak habis dibagi $7$), tambahkan ruas kanan dengan $7$
$5x \equiv 8 \pmod{7}$      ($8$ tidak habis dibagi $7$), tambahkan ruas kanan dengan $7$
$5x \equiv 15 \pmod{7}$    ($15$ habis dibagi $7$), bagi kedua ruas dengan $5$
$x \equiv 3 \pmod{7}$

Jadi, solusi persamaan ini adalah $x \equiv 3 \pmod{7}$


Soal 3
Carilah solusi dari persamaan $14x \equiv 3 \pmod{81}$

Solusi
Perhatikan bahwa

$14x \equiv 3 \pmod{81}$     Tambahkan ruas kanan dengan $81$
$14x \equiv 84 \pmod{81}$   Bagi kedua ruas dengan $14$
$x \equiv 6 \pmod{81}$

Jadi solusi persamaan ini adalah $x \equiv 6 \pmod{81}$


Soal 4
Carilah penyelesaian dari sistem persamaan $x \equiv 8 \pmod{15}$ dan $x \equiv 3 \pmod{8}$

Solusi
Carilah KPK antara $15$ dan $8$ terlebih dahulu yaitu $120$. Setelah itu, samakan kedua persamaan sedemikian sehingga persamaan tersebut sekarang memiliki modulo dalam KPK kedua bilangan yang tadi. Oleh karena itu, kalikan persamaan $1$ dengan $8$ dan persamaan $2$ dengan $15$ akibatnya diperoleh

$8x \equiv 64 \pmod{120}$ dan $15x \equiv 45 \pmod{120}$

Kurangkan kedua persamaan sehingga diperoleh

$7x \equiv -19 \pmod{120}$     Tambahkan ruas kanan dengan $120$
$7x \equiv 101 \pmod{120}$      Tambahkan ruas kanan dengan $120$
$7x \equiv 221 \pmod{120}$      Tambahkan ruas kanan dengan $120$
$7x \equiv 341 \pmod{120}$      Tambahkan ruas kanan dengan $120$
$7x \equiv 461 \pmod{120}$      Tambahkan ruas kanan dengan $120$
$7x \equiv 581 \pmod{120}$       Bagi kedua ruas dengan $7$
$x \equiv 83 \pmod{120}$

Jadi solusi persamaan ini adalah $x \equiv 6 \pmod{81}$


Soal 5
Selesaikan sistem persamaan $x \equiv 1 \pmod{2}$, $x \equiv 1 \pmod{3}$, dan $x \equiv 1 \pmod{5}$

Solusi
Perhatikan bahwa dari sistem diatas diperoleh $x - 1 \equiv 0 \pmod{2}$, $x - 1 \equiv 0 \pmod{3}$, dan $x - 1 \equiv 0 \pmod{5}$. Dari persamaan diatas terlihat bahwa $x - 1$ habis dibagi oleh $2, 3$ dan $5$. Jadi,  haruslah $x - 1 \equiv 0 \pmod{30}$.

Sehingga, solusi sistem persamaan ini adalah $x \equiv 1 \pmod{30}$


Soal 6
Selesaikan sistem persamaan $x \equiv 1 \pmod{2}$, $x \equiv 2 \pmod{3}$, dan $x \equiv 4 \pmod{5}$

Solusi
Perhatikan bahwa dari sistem diatas diperoleh $x + 1 \equiv 0 \pmod{2}$, $x + 1 \equiv 0 \pmod{3}$, dan $x + 1 \equiv 0 \pmod{5}$. Dari persamaan diatas terlihat bahwa $x + 1$ habis dibagi oleh $2, 3$ dan $5$. Jadi,  haruslah $x + 1 \equiv 0 \pmod{30}$.

Sehingga, solusi sistem persamaan ini adalah $x \equiv 29 \pmod{30}$


Soal 7
Hitunglah penyelesaian sistem persamaan $3x + 4y \equiv 5 \pmod{13}$ dan $2x + 5y \equiv 7 \pmod{13}$

Solusi
Agar variabel $y$ hilang, tentu akan dilakukan proses eliminasi dengan mengalikan persamaan pertama dengan $5$ dan persamaan kedua dengan $4$ dan kemudian mengurangannya sehingga diperoleh

$5(3x + 4y) - 4(2x + 5y) \equiv 25 - 28 \pmod{13} \implies 7x \equiv 10 \pmod{13}$

Selesaikan persamaan ini dengan cara biasa sehingga diperoleh $x \equiv 7 \pmod{13}$. Lakukan hal yang sama untuk $y$ sehingga diperoleh $y \equiv 9 \pmod{13}$

Jadi, solusi persamaan ini adalah $(x, y)$ dengan  $x \equiv 7 \pmod{13}$ dan $y \equiv 9 \pmod{13}$


Soal 8
$100$ jika dibagi $y$ memberikan sisa $4$, sedangkan $90$ jika dibagi $y$ memberikan sisa $10$. Tentukan nilai dari $y$.

Solusi
Soal diatas menghasilkan $2$ sistem persamaan yaitu $y|96$ dan $y|80$. Perhatikan bahwa FPB dari $96$ dan $80$ adalah $16$. Padahal dengan menggunakan definisi FPB diperoleh $y|16$. Karena $y > 10$ (Berdasarkan soal). Maka, satu - satunya kemungkinan nilai dari $y$ adalah $16$

Jadi $y = 16$



Berikut saya tambahkan latihan supaya pembaca menjadi lebih paham
Soal 1
Carilah penyelesaian dari masing - masing persamaan :
(a) $5x \equiv 4 \pmod{11}$
(b) $3x \equiv 7 \pmod{17}$
(c) $9x \equiv 4 \pmod{49}$
(d) $100x \equiv 7 \pmod{121}$

Soal 2
Selesaikan sistem persamaan berikut
(a) $x \equiv 1 \pmod{2}$ dan $x \equiv 2 \pmod{3}$
(b) $3x \equiv 1 \pmod{5}$ dan $2x \equiv 3 \pmod{7}$
(c) $x \equiv 5 \pmod{15}$ dan $4x \equiv 7 \pmod{11}$
(d) $2x \equiv 3 \pmod{5}$ dan $7x \equiv 9 \pmod{13}$

Soal 3
Selesaikan sistem persamaan berikut
(a) $2x \equiv 1 \pmod{3}$, $3x \equiv 4 \pmod{5}$, dan $3x \equiv 7 \pmod{8}$
(b) $2x \equiv 1 \pmod{3}$, $3x \equiv 5 \pmod{13}$, dan $7x \equiv 9 \pmod{25}$

Soal 4
Tentukan bilangan asli terkecil yan memenuhi sifat : Jika dibagi oleh $6, 5, 4, 3$, dan $2$ maka secara berturut - turut akan memberikan sisa $5, 4, 3, 2,$ dan $1$.