A Bunch of Irreducible Fractions
Find the smallest positive integer value of n for which all of the fractions n + 9 7 , n + 1 0 8 , n + 1 1 9 , n + 1 2 1 0 , … , n + 2 0 1 6 2 0 1 4 are in lowest terms.
The answer is 2015.
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
2 solutions
Shouldn't it be gcd(m, m+n) =1?
Log in to reply
He used the fact that g cd ( m , m + n ) = g cd ( m , n ) .
The +2 arose because we are actually comparing g cd ( m , m + n + 2 ) = g cd ( m , n + 2 ) .
Smallest value of N should be "-3" so that each fraction would be of form M − 1 M and thus each fraction will be in lowest terms because two consecutive number are always Co-Prime. Proof Here
By division algorithm, we find that n+2 must be coprime to 7,9,10,...,2014. It follows that n must not be in the set {1,2,3,...,2014} since m/(n+m+2) is in lowest terms. Hence, n+2 must be the smallest prime greater than 2014. Thus, n+2 =2017. Therefore, n=2015.
If q p is in lowest terms, then g cd ( p , q ) = 1 . Since each fraction is of the form m + n + 2 m , we must have g cd ( n + 2 , m ) = 1 for all m ∈ [ 7 , 2 0 1 4 ] . The smallest integer that is relatively prime to every integer in this interval is the smallest prime larger than 2 0 1 4 , which is 2 0 1 7 . This is two more than n , so n is 2 0 1 5 .