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 19: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.
