The first problem in the first International Mathematical Olympiad was this.
Prove that is irreducible for every .
Show/hide the solution.
Note that . By Bézout’s identity, 1 is the greatest common divisor of and . Hence the fraction is irreducible.
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.
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 .