Soal 3

Buktikan bahwa $\large{\frac{21n+4}{14n+3}}$ tidak dapat disederhanakan lagi

Sumber: International Math Olympiad 1959 - Problem 1

Solusi

Misalkan $a=21n+4$ dan $b=14n+3$
Asumsikan $\large{\frac{a}{b}}$ masih dapat disederhanakan lagi. Yaitu, $gcd(a,b) \gt 1$

Maka:
$a=gcd(a,b).p$ dan
$b=gcd(a,b).q$

Maka:
$3b-2a=gcd(a,b).(3q-2p)$
$(42n+9)-(42n+8)=gcd(a,b).(3q-2p)$
$1=gcd(a,b).(3q-2p)$

Karena sisi kiri nilainya $1$ dan $gcd(a,b)\gt 1$ terjadi kontradiksi

Dengan demikian, asumsi awal kita salah dan $gcd(a,b)$ tidak boleh lebih besar dari $1$

Dengan demikian, $\large{\frac{21n+4}{14n+3}}$ tidak dapat disederhanakan lagi