Generalizing Problem 1 from the 1959 IMO

The first problem in the first International Mathematical Olympiad was this.

Prove that $\frac{21n+4}{14n+3}$ is irreducible for every $n$ .

Solution

Show/hide the solution.

Note that $3(14n+3) - 2(21n+4) = 1$ . By Bézout’s identity, 1 is the greatest common divisor of $14n + 3$ and $21n + 4$ . Hence the fraction is irreducible.

A Generalization

What other fractions of the form $\frac{an+b}{cn+d}$ are irreducible for every natural number $n$ ?

This amounts to looking for a prime $p$ such that the following system of congruences, call it $\mathcal{S}_p$ , has a solution.

$\begin{align*}an + b \equiv 0 \pmod{p} \\cn + d \equiv 0 \pmod{p}\end{align*}$

Let $p$ be a prime that divides neither $a$ nor $c$ . Then $a$ and $c$ have inverses modulo $p$ , and we can solve each congruence for $n$ .

$\begin{align*}n \equiv -ba^{-1} \pmod{p} \\n \equiv -dc^{-1} \pmod{p}\end{align*}$

If $n$ is a solution to both congruences then we have

$\begin{align*}dc^{-1} \equiv ba^{-1} \pmod{p} \\ad \equiv bc \pmod{p} \\ad - bc \equiv 0 \pmod{p}\end{align*}$

This shows that if $p$ doesn’t divide $ac$ and $\mathcal{S}_p$ has a solution, then $p$ divides $ad - bc$ . Therefore we only have to check primes that divide $a$ , $c$ , or $ad-bc$ .

If $p$ is a prime that divides $a$ then $an + b \equiv 0 \pmod{p}$ if and only if $p$ divides $b$ . If this is the case, then any $n$ satisfies $an + b \equiv 0 \pmod{p}$ . To simultaneously solve $cn + d \equiv 0 \pmod{p}$ , it is required that either (1) $p$ divides both $c$ and $d$ or (2) $p$ doesn’t divide $c$ , in which case any $n$ such that $n \equiv -dc^{-1} \pmod{p}$ solves $\mathcal{S}_p$ . Mutatis mutandis for primes that divide $c$ .

Now suppose there is a prime $p$ that divides $ad - bc$ but doesn’t divide $a$ or $c$ . Then we can solve each congruence directly. We can use the fact that $a^{-1} \equiv a^{p-2} \pmod{p}$ , which is equivalent to Fermat’s little theorem.

$\begin{align*}an + b \equiv 0 \pmod{p} \\an \equiv -b \pmod{p} \\n \equiv -ba^{p-2} \pmod{p}\end{align*}$

If such an $n$ also satisfies $cn + d \equiv 0 \pmod{p}$ , then the fraction is reducible.

Examples

1. Is $\frac{7n+21}{4n+5}$ irreducible for every $n$ ?

7 divides the numerator but does not divide 4. Therefore we can solve $4n + 5 \equiv 0 \pmod{7}$ to find an $n$ that will make the fraction reducible:

$\begin{align*}4n + 5 \equiv 0 \pmod{7} \\4n \equiv 2 \pmod{7} \\n \equiv 2^{-1} \pmod{7} \\n \equiv 2^{7-2} \pmod{7} \\n \equiv 4 \pmod{7}\end{align*}$

Therefore any $n$ such that $n \equiv 4 \pmod{7}$ will make the fraction reducible.

2. Is $\frac{3n+2}{5n+7}$ irreducible for every $n$ ?

We have to check 3 and 5. By inspection it is clear that neither 3 nor 5 divide both numerator and denominator. Next we check primes that divide $ad - bc = 3\cdot 7 - 2\cdot 5 = 11$ . So we must look for solutions to

$\begin{align*}3n+2 \equiv 0 \pmod{11} \\7n+5 \equiv 0 \pmod{11}\end{align*}$

We solve the first congruence:

$\begin{align*}3n+2 \equiv 0 \pmod{11} \\3n \equiv 9 \pmod{11} \\n \equiv 3 \pmod{11}\end{align*}$

Substituting $n = 3$ into the second congruence we get $7\cdot 3+5 = 26 \not\equiv 0 \pmod{11}$ . The system is not satisfied, therefore $\frac{3n+2}{5n+7}$ is irreducible for every $n$ .

3. Is $\frac{2n+1}{3n+5}$ irreducible for every $n$ ?

Neither 2 nor 3 divide both the numerator and denominator. $ad - bc = 2\cdot 5 - 3\cdot 1 = 7$ . We solve $2n + 1 \equiv 0 \pmod{7}$ and obtain $n = 3$ . This also satisfies $3n + 5 \equiv 0 \pmod{7}$ since $3\cdot 3 + 5 = 14 \equiv 0 \pmod{7}$ . Therefore $\frac{2n+1}{3n+5}$ is reducible when $n \equiv 3 \pmod{7}$ .

Solution

A Generalization

Examples

Leave a Reply Cancel reply