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