$\frac{7x+1}2, \frac{7x+2}3, \frac{7x+3}4, \ldots ,\frac{7x+2016}{2017}$ are reduced fractions for integers $x\in(0,301)$.

Question

BdMO 2017 junior catagory Question 7. $$\dfrac{7x+1}2, \dfrac{7x+2}3, \dfrac{7x+3}4, \ldots ,\dfrac{7x+2016}{2017}$$ Here $x$ is a positive integer and $x < 301$. For some values of $x$ it is possible to express these given fraction in such fraction where denominator and numerator are co-prime. How many such $x$ is possible?

For an example if $x=4$, then $\dfrac{7x+1}2 = \dfrac{28+1}2 = \dfrac{29}2$. Here $29$ and $2$ are co-primes. But in the third term of this pattern I've noticed that $\dfrac{28+2}3 = \dfrac{30}3$ where $30$ and $3$ are not co-primes. So, $x$ is not $4$.

Answer 1

As noted by lab bhattacharjee, we need to see if $7x-1$ is co-prime to all $k=2,3,\ldots,2017$. If $0<x<301$, then $6\le 7x-1\le 7\times 300-1=2099$. Clearly, an integer in the interval $[6,2017]$ is not co-prime to all of the integers in $[2,2017]$ (in other words, $t$ is not co-prime to $t$ for $t\ge 2$). So we have to worry about $x$s such that $2017<7x-1\le 2099$, that is, $289\le x\le 300$. Plus if $x$ is odd, $7x-1$ is even so it is not co-prime to $2$. There are only $6$ integers remaining, and the list of $7x-1$ is as shown below.

1. $x=290$ so $7x-1=2029$ is prime so it is a good candidate.

2. $x=292$ so $7x-1=2043$ is not co-prime to $3$.

3. $x=294$ so $7x-1=2057$ is not co-prime to $11$.

4. $x=296$ so $7x-1=2071$ is not co-prime to $19$.

5. $x=298$ so $7x-1=2085$ is not co-prime to $5$.

6. $x=300$ so $7x-1=2099$ is prime so it is another good candidate.

Therefore there are only two good $x$s: $x=290$ and $x=300$.

Answer 2

Assume $n, m$ are positive integers such that $n<m$. Given a fraction $\frac{m}{n}$, where $\gcd(m, n)=g<n$, this fraction can be simplified to a a fraction with co-prime numerator and denominator by dividing both $m$ and $n$ by $g$, i.e., $\gcd(\frac{m}{g}, \frac{n}{g})=1$.

In our case, we need to find all $x<301$ such that for all $i=1, 2, ..., 2016$: $$\gcd(7x+i, i+1) < i+1$$ as $i+1$ is the smaller of the two.

Since $\gcd(a, b)=\gcd(a-b,b)$ we get $$\gcd(7x+i,i+1)=\gcd(7x-1,i+1)<i+1.$$ If $i+1$ is prime, this becomes $$\gcd(7x-1, i+1)=1$$ because $1$ is the only factor of a prime number less than the number itself. As long as the chosen number $x$ satisfies the above equality for all primes between $2$ and $2017$ then it will automatically satisfy it for all other numbers in the same range (as every other number will be a product of some of these primes).

Now notice that if $7x-1\leq 2017$ then there will always be a number, namely, $i=7x-2<2017$, that will make the above equality fail ($\gcd(a,a)=a>1$). So we need $7x-1>2017$, which means that $x\geq 289$. Also notice that if $x$ is odd, then the first fraction would simplify. So all is left to check are the numbers $\{290, 292, 294, 296, 298, 300\}$.

The only solutions are $290$ and $300$.