Tentukan solusi dari 6789783x = 1237005 ( mod 28927591 )

Tentukan solusi dari 6789783x = 1237005 ( mod 28927591 )

Jawaban Terkonfirmasi

Solusi dari 6789783x ≡ 1237005 (mod 28927591) adalah:
$largetext{$begin{aligned}boxed{,247xequiv45 (!!!!mod3157),}end{aligned}$}$

Solusi final yang diperoleh adalah:
$largetext{$begin{aligned}boxed{,x=3157n+537,, ninmathbb{Z},}end{aligned}$}$
 

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.

$6789783 = 3!times!7^2!times!11!times!13!times!17!times!19$
$1237005 = 3^3!times!5!times!7^2!times!11!times!17$
$28927591 = 7^3!times!11^2!times!17!times!41$

Maka,

$begin{aligned}&6789783xequiv 1237005 (!!!!mod 28927591)\&............................................................\&left(3!times!7^2!times!11!times!13!times!17!times!19right)x\&equivleft(3^3!times!5!times!7^2!times!11!times!17right)\&qquadleft(!!!!mod 7^3!times!11^2!times!17!times!41right)\&............................................................\end{aligned}$

Pada aritmetika modular, aturan pembagian yang berlaku adalah:

$begin{aligned}frac{a}{e}equivfrac{b}{e} left(!!!!modfrac{m}{{rm fpb}(m,e)}right)end{aligned}$

Dalam hal ini, $a=6789783$ , $b=1237005$ , $m=28927591$ .

Karena $e$ adalah bilangan bulat yang habis membagi $a$ dan $b$ , maka $e={rm fpb}(a,b)$ , sehingga

$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!19right),left(3^3!times!5!times!7^2!times!11!times!17right)right)\&=3!times!7^2!times!11!times!17end{aligned}$

Lalu,

$begin{aligned}&{rm fpb}(m,e)\&={rm fpb}left(28927591,left(3!times!7^2!times!11!times!17right)right)\&={rm fpb}left(left(7^3!times!11^2!times!17!times!41right),left(3!times!7^2!times!11!times!17right)right)\&=7^2!times!11!times!17end{aligned}$

Melanjutkan perhitungan kongruensi modular di atas dengan aturan pembagian, kita peroleh:

$begin{aligned}&frac{left(cancel{3!times!7^2}!times!cancel{11}!times!13!times!cancel{17}!times!19right)x}{cancel{left(3!times!7^2!times!11!times!17right)}}\&equivfrac{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)}\&qquadleft(!!!!mod frac{7^3!times!11^2!times!cancel{17}!times!41}{7^2!times!11!times!cancel{17}}right)end{aligned}$
$begin{aligned}&............................................................\&(13!times!19)xequivleft(3^2!times!5right) (!!!!mod7!times!11!times!41)\&............................................................\&therefore 247xequiv45 (!!!!mod3157)\&Rightarrow x=frac{3157k+45}{247}, kinmathbb{Z}\&............................................................end{aligned}$

$247xequiv45 (!!!!mod3157)$ atau $x=dfrac{3157k+45}{247}$ dengan $kinmathbb{Z}$ adalah solusinya. Namun, kita masih bisa menganggapnya belum final. Kita dapat menelusuri nilai-nilai $kinmathbb{Z}$ sehingga memperoleh $x$ bilangan bulat.

Dengan nilai-nilai positif, diperoleh $k$ pertama yang memenuhi adalah $k=42$ .

$begin{aligned}x&=frac{3157cdot42+45}{247}\&=frac{132639}{247}\x&=537=bf3157cdot0+537end{aligned}$

Kemudian, $k$ kedua yang diperoleh adalah $k=247+42=289$ .

$begin{aligned}x&=frac{3157cdot289+45}{247}\&=frac{912418}{247}\x&=3694=bf3157cdot1+537end{aligned}$

Jika kita menelusuri pada nilai negatif, diperoleh $k=-247+42=-205$ .

$begin{aligned}x&=frac{3157cdot(-205)+45}{247}\&=frac{-647140}{247}\x&={-}2620=bf3157cdot(-1)+537end{aligned}$

Dengan hasil tersebut, solusi finalnya adalah:

$largetext{$begin{aligned}therefore boxed{,x=3157n+537,, ninmathbb{Z},}end{aligned}$}$

$blacksquare$

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