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}.

Leave a Reply

Your email address will not be published. Required fields are marked *