## Tuesday, January 24, 2006

### 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$.