Difference between revisions of "1959 IMO Problems/Problem 1"
m (correction in problem) |
|||
Line 4: | Line 4: | ||
− | == Solution == | + | == Solutions == |
+ | |||
+ | === First Solution === | ||
We observe that | We observe that | ||
<center> | <center> | ||
− | <math>\displaystyle 3(14n+3) = 2(21n+4) + 1 | + | <math>\displaystyle 3(14n+3) = 2(21n+4) + 1.</math> |
</center> | </center> | ||
− | |||
+ | Since a multiple of <math>\displaystyle 14n+3</math> differs from a multiple of <math>\displaystyle 21n+4</math> by 1, we cannot have any postive integer greater than 1 simultaneously divide <math>\displaystyle 14n+3</math> and <math>\displaystyle 21n+4</math>. 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 <math>\displaystyle a, b </math> as <math>\displaystyle (a,b) </math>, we use the [[Euclidean algorithm]] as follows: | ||
+ | |||
+ | <center> | ||
+ | <math>\displaystyle ( 21n+4, 14n+3 ) = ( 7n+1, 14n+3 ) = ( 7n+1, 1 ) = 1 </math> | ||
+ | </center> | ||
+ | |||
+ | As in the first solution, it follows that <math>\frac{21n+4}{14n+3}</math> is irreducible. Q.E.D. | ||
== Resources == | == Resources == |
Revision as of 20:16, 25 July 2006
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.