4
$\begingroup$

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

$\endgroup$

closed as off-topic by Namaste, zipirovich, mrtaurho, KReiser, Lee David Chung Lin Jan 9 at 10:12

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question is missing context or other details: Please provide additional context, which ideally explains why the question is relevant to you and our community. Some forms of context include: background and motivation, relevant definitions, source, possible strategies, your current progress, why the question is interesting or important, etc." – Namaste, zipirovich, mrtaurho, KReiser, Lee David Chung Lin
If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ What do you mean? Any rational number can be written in the way you want, no? $\endgroup$ – lulu Jan 8 at 14:36
  • $\begingroup$ $7x+\dfrac12$ or$\dfrac{7x+1}2$ $\endgroup$ – lab bhattacharjee Jan 8 at 14:39
  • $\begingroup$ $\dfrac{7x+1}2$ $\endgroup$ – Shromi Jan 8 at 14:44
  • $\begingroup$ Your question isn't clear. Perhaps it would help to try an example. Is $x=1$ an example of what you want? Why or why not? $\endgroup$ – lulu Jan 8 at 14:45
  • 2
    $\begingroup$ So, we need $$(7x-1,n)=1$$ sufficient to check for primes $\le2017$ $\endgroup$ – lab bhattacharjee Jan 8 at 14:47
1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Thanks for answer. But it hard for an 8th grade student to understand such an answer. Could you make it simple. $\endgroup$ – Shromi Jan 8 at 16:17
  • $\begingroup$ Is there any part in particular where you got lost? $\endgroup$ – EuxhenH Jan 8 at 16:33

Not the answer you're looking for? Browse other questions tagged or ask your own question.