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

1. Why do you need to prove that lemma? It's really really well-known.

2. Is it me or is that the easiest IMO problem in history

3. To chess64: Yes, it is really well known, but the proof is so short it doesn't really matter. And to a beginner at number theory, I doubt the conclusion is COMPLETELY obvious.

To Anonymous: Probably close; it's from the first IMO in history also.

4. u = 7n + 1. o.o