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