Mfrhtyj

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$.

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 $6le 7x-1le 7times 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 $tge 2$). So we have to worry about $x$s such that $2017<7x-1le 2099$, that is, $289le xle 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$.

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-1leq 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 $xgeq 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$.