Olimpiade Sains Kota (OSK) 2015 - Matematika SMA, Nomor 11

Karena n adalah bilangan asli, maka untuk n = 1

(31 + 96x) mod 2015 = 0

Untuk menghasilkan sisa nol, 31 + 96x haruslah kelipatan 2015, jadi dapat ditulis

31 + 96x = 2015k

31 = 2015k - 96x

Kita telah mendapatkan suatu persamaan Diophantine. Persamaan Diophantine akan mempunyai solusi jika FPB dari 96 dan 2015 adalah 1. Salah satu cara menemukan FPB adalah dengan Algoritma Euclid.

2015 = 96(20) + 95

96 = 95(1) + 1 (berhenti)

Ternyata FPB dari 2015 dan 95 adalah 1, maka persamaan tersebut dapat diselesaikan. Lalu kita ubah bentuk algoritma yang tadi menjadi

1 = 96 + 95(-1)

2015 = 96(20) + 95 → 95 = 2015 + 96(-20). Lalu subtitusikan.

1 = 96 + (2015 + 96(-20))(-1)

1 = 96 + 2015(-1) + 96(20)

1 = 96(21) + 2015(-1)

1 = 2015(-1) - 96(-21) 

[Kalikan semua ruas dengan 31]

31 = 2015(-31) - 96(-651)

Didapatkan k = -31 dan x = -651. Tetapi, x haruslah bilangan positif. Persamaan Diophantine tersebut juga memiliki solusi lain yaitu:

31 = 2015(-31 + 96) - 96(-651 + 2015)

31 = 2015(65) - 96(1.364)

Didapatkan nilai x = 1.364

1364