1959 IMO Problems/Problem 1
Prove that the fraction is irreducible for every natural number .
Denoting the greatest common divisor of as , we use the Euclidean algorithm as follows:
As in the first solution, it follows that is irreducible. Q.E.D.
Hence is irreducible. Q.E.D.
We notice that:
So it follows that and must be coprime for every natural number for the fraction to be irreducible. Now the problem simplifies to proving irreducible. We re-write this fraction as:
Since the denominator differs from a multiple of the numerator by 1, the numerator and the denominator must be relatively prime natural numbers. Hence it follows that is irreducible.
By Bezout's Lemma, , so the GCD of the numerator and denominator is and the fraction is irreducible.
Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.
|1959 IMO (Problems) • Resources)|
|1 • 2 • 3 • 4 • 5 • 6||Followed by|
|All IMO Problems and Solutions|