Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "1959 IMO Problems/Problem 1"
(template)
Line 1: Line 1:
 
== Problem ==
 
== Problem ==
  
−
Prove that the fraction <math>\frac{21n+4}{14n+3}</math> is irreducible for every natural number <math>\displaystyle n</math>.
+
Prove that the fraction <math>\frac{21n+4}{14n+3}</math> is irreducible for every natural number <math>n</math>.
  
  
Line 11: Line 11:
  
 
<center>
 
<center>
−
<math>\displaystyle 3(14n+3) = 2(21n+4) + 1.</math>
+
<math>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.
+
Since a multiple of <math>14n+3</math> differs from a multiple of <math>21n+4</math> by 1, we cannot have any postive integer greater than 1 simultaneously divide <math>14n+3</math> and <math>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 ===
 
=== 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:
+
Denoting the greatest common divisor of <math>a, b </math> as <math>(a,b) </math>, we use the [[Euclidean algorithm]] as follows:
  
 
<center>
 
<center>
−
<math>\displaystyle ( 21n+4, 14n+3 ) = ( 7n+1, 14n+3 ) = ( 7n+1, 1 ) = 1 </math>
+
<math>( 21n+4, 14n+3 ) = ( 7n+1, 14n+3 ) = ( 7n+1, 1 ) = 1 </math>
 
</center>
 
</center>
  
 
As in the first solution, it follows that <math>\frac{21n+4}{14n+3}</math> is irreducible.  Q.E.D.
 
As in the first solution, it follows that <math>\frac{21n+4}{14n+3}</math> is irreducible.  Q.E.D.
  
−
== Resources ==
 
−
* [[1959 IMO Problems]]
 
−
* [http://www.artofproblemsolving.com/Forum/viewtopic.php?p=341470#p341470 Discussion on AoPS/MathLinks]
 
  
 +
{{IMO box|year=1959|before=First question|num-a=2}}
  
 
[[Category:Intermediate Algebra Problems]]
 
[[Category:Intermediate Algebra Problems]]

Revision as of 20:21, 25 October 2007

Problem

Prove that the fraction $\frac{21n+4}{14n+3}$ is irreducible for every natural number $n$.


Solutions

First Solution

We observe that

$3(14n+3) = 2(21n+4) + 1.$


Since a multiple of $14n+3$ differs from a multiple of $21n+4$ by 1, we cannot have any postive integer greater than 1 simultaneously divide $14n+3$ and $21n+4$. 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 $a, b$ as $(a,b)$, we use the Euclidean algorithm as follows:

$( 21n+4, 14n+3 ) = ( 7n+1, 14n+3 ) = ( 7n+1, 1 ) = 1$

As in the first solution, it follows that $\frac{21n+4}{14n+3}$ is irreducible. Q.E.D.


1959 IMO (Problems) • Resources
Preceded by
First question 		1 • 2 • 3 • 4 • 5 • 6 Followed by
Problem 2
All IMO Problems and Solutions
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=1959_IMO_Problems/Problem_1&oldid=18749"