Solusi dari 6789783x ≡ 1237005 (mod 28927591) adalah:
[tex]\large\text{$\begin{aligned}\boxed{\,247x\equiv45\ (\!\!\!\!\mod3157)\,}\end{aligned}$}[/tex]
Solusi final yang diperoleh adalah:
[tex]\large\text{$\begin{aligned}\boxed{\,x=3157n+537\,,\ \ n\in\mathbb{Z}\,}\end{aligned}$}[/tex]
Pembahasan
Teori Bilangan: Aritmetika Modular
Diketahui
6789783x ≡ 1237005 (mod 28927591)
Ditanyakan
Solusi dari kongruensi modular tersebut
Penyelesaian
Terlebih dahulu kita cari faktorisasi prima dari 6789783, 1237005, dan 28927591.
- [tex]6789783 = 3\!\times\!7^2\!\times\!11\!\times\!13\!\times\!17\!\times\!19[/tex]
- [tex]1237005 = 3^3\!\times\!5\!\times\!7^2\!\times\!11\!\times\!17[/tex]
- [tex]28927591 = 7^3\!\times\!11^2\!\times\!17\!\times\!41[/tex]
Maka,
[tex]\begin{aligned}&6789783x\equiv 1237005\ \ (\!\!\!\!\mod 28927591)\\&............................................................\\&\left(3\!\times\!7^2\!\times\!11\!\times\!13\!\times\!17\!\times\!19\right)x\\&\equiv\left(3^3\!\times\!5\!\times\!7^2\!\times\!11\!\times\!17\right)\\&\qquad\left(\!\!\!\!\mod 7^3\!\times\!11^2\!\times\!17\!\times\!41\right)\\&............................................................\\\end{aligned}[/tex]
Pada aritmetika modular, aturan pembagian yang berlaku adalah:
[tex]\begin{aligned}\frac{a}{e}\equiv\frac{b}{e}\ \ \left(\!\!\!\!\mod\frac{m}{{\rm fpb}(m,e)}\right)\end{aligned}[/tex]
Dalam hal ini, [tex]a=6789783[/tex], [tex]b=1237005[/tex], [tex]m=28927591[/tex].
Karena [tex]e[/tex] adalah bilangan bulat yang habis membagi [tex]a[/tex] dan [tex]b[/tex], maka [tex]e={\rm fpb}(a,b)[/tex], sehingga
[tex]\begin{aligned}e&={\rm fpb}(a,b)\\&={\rm fpb}(6789783,1237005)\\&={\rm fpb}\left(\left(3\!\times\!7^2\!\times\!11\!\times\!13\!\times\!17\!\times\!19\right),\left(3^3\!\times\!5\!\times\!7^2\!\times\!11\!\times\!17\right)\right)\\&=3\!\times\!7^2\!\times\!11\!\times\!17\end{aligned}[/tex]
Lalu,
[tex]\begin{aligned}&{\rm fpb}(m,e)\\&={\rm fpb}\left(28927591,\left(3\!\times\!7^2\!\times\!11\!\times\!17\right)\right)\\&={\rm fpb}\left(\left(7^3\!\times\!11^2\!\times\!17\!\times\!41\right),\left(3\!\times\!7^2\!\times\!11\!\times\!17\right)\right)\\&=7^2\!\times\!11\!\times\!17\end{aligned}[/tex]
Melanjutkan perhitungan kongruensi modular di atas dengan aturan pembagian, kita peroleh:
[tex]\begin{aligned}&\frac{\left(\cancel{3\!\times\!7^2}\!\times\!\cancel{11}\!\times\!13\!\times\!\cancel{17}\!\times\!19\right)x}{\cancel{\left(3\!\times\!7^2\!\times\!11\!\times\!17\right)}}\\&\equiv\frac{\left(3^3\!\times\!5\!\times\!\cancel{7^2\!\times\!11\!\times\!17}\right)}{\left(3\!\times\!\cancel{7^2\!\times\!11\!\times\!17}\right)}\\&\qquad\left(\!\!\!\!\mod \frac{7^3\!\times\!11^2\!\times\!\cancel{17}\!\times\!41}{7^2\!\times\!11\!\times\!\cancel{17}}\right)\end{aligned}[/tex]
[tex]\begin{aligned}&............................................................\\&(13\!\times\!19)x\equiv\left(3^2\!\times\!5\right)\ (\!\!\!\!\mod7\!\times\!11\!\times\!41)\\&............................................................\\&\therefore\ 247x\equiv45\ (\!\!\!\!\mod3157)\\&\Rightarrow\ x=\frac{3157k+45}{247},\ \ k\in\mathbb{Z}\\&............................................................\end{aligned}[/tex]
[tex]247x\equiv45\ (\!\!\!\!\mod3157)[/tex] atau [tex]x=\dfrac{3157k+45}{247}[/tex] dengan [tex]k\in\mathbb{Z}[/tex] adalah solusinya. Namun, kita masih bisa menganggapnya belum final. Kita dapat menelusuri nilai-nilai [tex]k\in\mathbb{Z}[/tex] sehingga memperoleh [tex]x[/tex] bilangan bulat.
Dengan nilai-nilai positif, diperoleh [tex]k[/tex] pertama yang memenuhi adalah [tex]k=42[/tex].
[tex]\begin{aligned}x&=\frac{3157\cdot42+45}{247}\\&=\frac{132639}{247}\\x&=537=\bf3157\cdot0+537\end{aligned}[/tex]
Kemudian, [tex]k[/tex] kedua yang diperoleh adalah [tex]k=247+42=289[/tex].
[tex]\begin{aligned}x&=\frac{3157\cdot289+45}{247}\\&=\frac{912418}{247}\\x&=3694=\bf3157\cdot1+537\end{aligned}[/tex]
Jika kita menelusuri pada nilai negatif, diperoleh [tex]k=-247+42=-205[/tex].
[tex]\begin{aligned}x&=\frac{3157\cdot(-205)+45}{247}\\&=\frac{-647140}{247}\\x&={-}2620=\bf3157\cdot(-1)+537\end{aligned}[/tex]
Dengan hasil tersebut, solusi finalnya adalah:
[tex]\large\text{$\begin{aligned}\therefore\ \boxed{\,x=3157n+537\,,\ \ n\in\mathbb{Z}\,}\end{aligned}$}[/tex]
[tex]\blacksquare[/tex]
Jawab:
(6789783, 28927591) = 9163 ⇔ ini artinya FPB dari kedua bilangan tersebut adalah 9163 [atau 7² × 11 × 17]
kita pakai angka FPB tersebut untuk sederhanakan persamaan 6789783x ≡ 1237005 (mod 28927591). di persamaan ini, kita diminta cari nilai x yang memenuhi 6789783x mod 28927591 = 1237005 mod 28927591 [tanda garis tiga beda sama tanda sama dengan]. persamaan itu disederhanakan menjadi:
741x ≡ 135 (mod 3157) ⇔ dibagi 9163
kita cek kalo (3157, 741) ga punya faktor yang sama, alias FPBnya = 1. ini artinya persamaan tersebut punya 1 solusi unik.
persamaan tersebut kita ubah jadi ke persamaan linear diophantine:
741x - 3157y = 135
nah untuk cari solusi dari persamaan ini, kita pakai algorithma euclidian:
3157 = 741 × 4 + 193 ⇔ angka 4 ini kita cari sendiri hasil perkalian 741 yang mendekati 3157, kemudian ditambah sisanya. tapi perlu ada angka 3157 sama 741. coba perhatiin pola selanjutnya...
3157 = 741 × 4 + 193
741 = 193 × 3 + 162 ⇔ nah,angka 741 sama angka 193 yang sebelumnya ada, kita pakai lagi di sini. tapi beda posisinya. lihat lagi pola selanjutnya
741 = 193 × 3 + 162
193 = 162 × 1 + 31 ⇔ di sini harusnya jelas polanya gimana, kita lanjut terus sampai akhir
193 = 162 × 1 + 31
162 = 31 × 5 + 7
31 = 7 × 4 + 3
7 = 3 × 2 + 1
3 = 1 × 3 ⇔ di sini akhirnya
dari pola tersebut kita bisa buat:
1 = 7 - 3 × 2 ⇔ ini diambil dari 7 = 3 × 2 + 1
1 = 7 - (31 - 7 × 4) × 2 = 9 × 7 - 31 × 2 ⇔ diambil dari 31 = 7 × 4 + 3. diubah komutatif. begitu terus selanjutnya sampai...
1 = 9 × 7 - 31 × 2
1 = 9 × (162 - 31 × 5) - 31 × 2 = 9 × 162 - 31 × 47
1 = 9 × 162 - (193 - 162 × 1) × 47 = 56 × 162 - 193 × 47
1 = 56 × (741 - 193 × 3) - 193 × 47 = 56 × 741 - 193 × 215
1 = 56 × 741 - (3157 - 741 × 4) × 215 = 916 × 741 - 3157 × 215
... sampai kita dapat lagi angka 741 sama 3157 nya. di sini persamaannya jadi:
1 = 916 × 741 - 3157 × 215
kita ubah susunan sedikit biar jadi:
741 × 916 - 3157 × 215 = 1
ingat, kalo kita perlu cari solusi untuk persamaan 741x - 3157y = 135. berarti, sekarang tinggal kita kali 135 aja persamaan yang kita susun tadi biar jadi
741 × 916 (× 135) - 3157 × 215 (× 135) = 1 (× 135)
741 × 123660 - 3157 × 29025 = 135
^
X, solusi yang dicari.
jadi, solusi dari 6789783x ≡ 1237005 (mod 28927591) adalah x = 123660
[answer.2.content]
