Difference between revisions of "1959 IMO Problems/Problem 1"
(→Solutions) |
|||
Line 31: | Line 31: | ||
[[Proof by contradiction]]: | [[Proof by contradiction]]: | ||
− | + | Assume that <math>\dfrac{14n+3}{21n+4}</math> is a [[reducible fraction]] where <math>p</math> is a [[divisor]] of both the [[numerator]] and the [[denominator]]: | |
<center> | <center> | ||
Line 62: | Line 62: | ||
</center> | </center> | ||
− | Since the denominator <math> 2(7n+1) + 1 </math> differs from a multiple of the numerator <math>7n+1</math> by 1, | + | Since the denominator <math> 2(7n+1) + 1 </math> differs from a multiple of the numerator <math>7n+1</math> by 1, the numerator and the denominator must be relatively prime natural numbers. Hence it follows that <math> \frac{21n+4}{14n+3}</math> is irreducible. |
Q.E.D | Q.E.D | ||
− | + | {{alternate solutions}} | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
== See Also == | == See Also == | ||
{{IMO box|year=1959|before=First question|num-a=2}} | {{IMO box|year=1959|before=First question|num-a=2}} |
Revision as of 14:15, 12 August 2014
Contents
Problem
Prove that the fraction is irreducible for every natural number .
Solutions
First Solution
We observe that
Since a multiple of differs from a multiple of by 1, we cannot have any postive integer greater than 1 simultaneously divide and . Hence the greatest common divisor of the fraction's numerator and denominator is 1, so the fraction is irreducible. Q.E.D.
Second Solution
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.
Third Solution
Assume that is a reducible fraction where is a divisor of both the numerator and the denominator:
Subtracting the second equation from the first equation we get which is clearly absurd.
Hence is irreducible. Q.E.D.
Fourth Solution
Let . Then where . Thus, . Note: This solution, in hindsight, is just the first solution above in a slightly different notation.
Fifth Solution
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.
Q.E.D
Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.
See Also
1959 IMO (Problems) • Resources | ||
Preceded by First question |
1 • 2 • 3 • 4 • 5 • 6 | Followed by Problem 2 |
All IMO Problems and Solutions |