SOLUTION: How many positive integers {{{ n }}} less than 2015 have the property that {{{ 1/3 + 1/n }}} can be simplified to a fraction with denominator less than {{{ n }}}?

Algebra.Com
Question 1037532: How many positive integers less than 2015 have the property that can be simplified to a fraction with denominator less than ?
Answer by Edwin McCravy(20056)   (Show Source): You can put this solution on YOUR website!
 = 

Certainly the denominator 3n is greater than n.  Therefore
the fraction must reduce.  Thus let d > 1 be the greatest
common divisor of n+3 and 3n, the numerator and denominator.

Then there exist positive integers k,m such that

n+3 = kd and 3n = md

So the fraction  reduces to , where m < n.

Then n = kd-3, and by substitution

3(kd-3) = md
3kd - 9 = md
 3kd-md = 9
d(3k-m) = 9
      d = 

So 3k-m is a divisor of 9, either 1, 3, or 9.

Since d > 1, 3k-m ≠ 9. So d is one of the
other two possibilities, d=3 or d=9

If d=3, then 3k-m = 3
   3k = m+3
    k = 

Since n+3 = kd,
n+3 = *3
n+3 = m+3
  n = m

But that contradicts m < n

So d=9, and 3k-m = 1
m = 3k-1
3n = md = dm
3n = 9(3k-1)
 n = 3(3k-1)
 n = 9k-3

Therefore n must be in the sequence 6,15,24,...,9k-3,...

n = 9k-3 ≤ 2015
      9k ≤ 2018
       k ≤ 224.2222...

So maximum value of k is 224,
thus the answer is 224.

Edwin

RELATED QUESTIONS

Conjecture: Find all positive integers 'a' such that there exists an integer 'm' with the (answered by richard1234)
The sum of the first n integers 1+2+3+...+n=n(n+1)/2 a.How many numbers must be taken to (answered by math_helper)
A polygon of n side has {{{n(n-3)/2}}} diagonals. How many sides has a polygon with 77... (answered by Edwin McCravy)
The sum of the first n integers 1 + 2 + 3 + ... + n = n(n + 1)/2 a How many... (answered by Fombitz,Edwin McCravy)
How many positive integers have exactly 3 proper divisors, each of which is less than 50? (answered by Edwin McCravy,CarlosOrtiz)
Can you please help me with those problems??? 1. Suppose that |a - b| + |b - c| + |c - (answered by chessace)
Let n!!! denote the product n*(n-3)*(n-6)*...*x where x is either 1, 2, or 3, if n is 1,... (answered by richard1234)
If N,E and T are distinct positive integers such that N*E*T =2013, then which of the... (answered by CubeyThePenguin)
If m and n are consecutive even integers and m > n > 0, how many integers are greater... (answered by Fombitz)