Difference between revisions of "1959 IMO Problems/Problem 1"
(→First Solution) |
(→First Solution) |
||
Line 14: | Line 14: | ||
EDIT: It appears to me that this solution is incorrect because it assumes that if <math>ax + b = cx + d</math>, then <math>a = c</math> and <math>b = d</math> -- the problem says irreducible for ALL <math>n</math>. If you agree, please remove this solution. 12/17/2017 | EDIT: It appears to me that this solution is incorrect because it assumes that if <math>ax + b = cx + d</math>, then <math>a = c</math> and <math>b = d</math> -- the problem says irreducible for ALL <math>n</math>. If you agree, please remove this solution. 12/17/2017 | ||
− | EDIT 2: Disregard the first edit, because when comparing two polynomials (linear functions in this case), the coefficients for each term must be equal to eachother. For example, in <math>ax^2+4=6x^2+b</math>, we must have <math>(a,b)=(6,4)</math>. Thus, if <math>ax+b=cx+d</math> for an unknown <math>x</math>, then <math>a</math> must equal <math>c</math> and <math>b</math> must equal <math>d</math>. | + | EDIT 2: Disregard the first edit, because when comparing two polynomials (linear functions in this case), the coefficients for each term must be equal to eachother. For example, if <math>x</math> can be any number, then in <math>ax^2+4=6x^2+b</math>, we must have <math>(a,b)=(6,4)</math>. Thus, if <math>ax+b=cx+d</math> for an unknown <math>x</math>, then <math>a</math> must equal <math>c</math> and <math>b</math> must equal <math>d</math>. |
=== Second Solution === | === Second Solution === |
Revision as of 01:06, 24 December 2017
Contents
[hide]Problem
Prove that the fraction is irreducible for every natural number .
Solutions
First Solution
For this fraction to be reducible there must be a number such that , and a such that . Since can only be one number ( is a linear term) we only have to evaluate for one of these equations. Using the first one, would have to equal . However, results in , and is not equal to our desired . Since there is no to make the numerator and denominator equal, we can conclude the fraction is irreducible.
EDIT: It appears to me that this solution is incorrect because it assumes that if , then and -- the problem says irreducible for ALL . If you agree, please remove this solution. 12/17/2017
EDIT 2: Disregard the first edit, because when comparing two polynomials (linear functions in this case), the coefficients for each term must be equal to eachother. For example, if can be any number, then in , we must have . Thus, if for an unknown , then must equal and must equal .
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
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 |