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

Prove that is irreducible for every .

## Solution

## Show/hide the solution.

Note that . By Bézout’s identity, 1 is the greatest common divisor of and . Hence the fraction is irreducible.

## A Generalization

What other fractions of the form are irreducible for every natural number ?

This amounts to looking for a prime such that the following system of congruences, call it , has a solution.

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

If is a solution to both congruences then we have

This shows that if doesn’t divide and has a solution, then divides . Therefore we only have to check primes that divide , , or .

If is a prime that divides then if and only if divides . If this is the case, then any satisfies . To simultaneously solve , it is required that either (1) divides both and or (2) doesn’t divide , in which case any such that solves . Mutatis mutandis for primes that divide .

Now suppose there is a prime that divides but doesn’t divide or . Then we can solve each congruence directly. We can use the fact that , which is equivalent to Fermat’s little theorem.

If such an also satisfies , then the fraction is reducible.

## Examples

1. Is irreducible for every ?

7 divides the numerator but does not divide 4. Therefore we can solve to find an that will make the fraction reducible:

Therefore any such that will make the fraction reducible.

2. Is irreducible for every ?

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 . So we must look for solutions to

We solve the first congruence:

Substituting into the second congruence we get . The system is not satisfied, therefore is irreducible for every .

3. Is irreducible for every ?

Neither 2 nor 3 divide both the numerator and denominator. . We solve and obtain . This also satisfies since . Therefore is reducible when .