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:
Their greatest common divisor is 1, so is irreducible. Q.E.D.
Subtracting the second equation from the first equation we get which is clearly absurd.
Hence is irreducible. Q.E.D.
Assume that is a reducible fraction.
If a certain fraction is reducible, then the fraction is reducible, too. In this case, .
This fraction consists of two consecutives numbers, which never share any factor. So in this case, is irreducible, which is absurd.
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.
To understand why its irreducible, let's take a closer look at the fraction itself. If we were to separate both fractions, we end up with + . Simplifying the fraction, we end up with. . Now combining these fractions with addition as shown before in the problem, we end up with . It's important to note that 17 is 1 off from being divisible by 6, and you'll see why later down this explanation. Now we expirement with some numbers. Plugging 1 in gives us . Notice how both numbers are one off from being divisible by 8(25 is next to 24, 17 is next to 16). Trying 2, we end up with . Again, both results are 1 off from being multiples of 15. Trying 3, we end up with . Again, both end up 1 away from being multiples of 22. This is where the realization comes in that two scenarios keep reoccurring:
1. Both Numerator and Denominator keep ending up 1 value away from being multiples of the same number, but
2. One always ends up being a prime number. Knowing that prime numbers only factors are 1 and itself, the fraction ends up being a paradoxical expression where one prime number is always being produced, and even with larger values, like say 15, implementing it in gives us , we keep ending up with results that at the end will only have a common divisor of 1.
Let So for some co-prime positive integers we have Multiplying by and by and then subtracting from we get We must have , since is an positive integer. Thus, which means the fraction is irreducible, as needed.
Video Solution by OmegaLearn
- little fermat
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|