Just Try and Reduce It. Topic: Number Theory. Level: AIME/Olympiad.

Problem: (1959 IMO - #1) Prove that the fraction $\frac{21n+4}{14n+3}$ is irreducible for every natural number $n$.

Solution: First, we're going to prove a very useful lemma.

**Lemma: For positive integers $a,b$, if there exist integers $x,y$ such that $ ax+by = 1 $ then $ gcd(a,b) = 1 $.

Proof: Let $ d = gcd(a,b) $. Then $ d|ax $ and $ d|by $ so $ d|(ax+by) \Rightarrow d|1 \Rightarrow gcd(a,b) = d = 1 $.**

Now, take $ a = 21n+4 $ and $ b = 14n+3 $. We find that $ (-2)(21n+4)+(3)(14n+3) = 1 $ so by Lemma, $ gcd(21n+4, 14n+3) = 1 $ and the fraction cannot be reduced. QED.

--------------------

Comment: Note that the lemma can be extended to iff. However, the reverse is considerably more difficult to prove, but still a good exercise in number theory.

--------------------

Practice Problem: Prove that for positive integers $ a,b $ such that $ gcd(a,b) = 1 $, there exist integers $ x,y $ such that $ ax+by = 1 $.