Count number

Number Theory Level 3

The number of positive integers $x$ with $x ≤ 60$ such that each of the rational expressions

$\frac{7x + 1}2, \frac{7x + 2}3,\frac{7x + 3}4, \cdots ,\frac{7x + 300}{301}$

is in lowest terms (i. e. in each expression , the numerator and denominator have no common factors) is:

2 4 1 5 3

1 solution

Alexander Shannon
Apr 18, 2020

Find $1 \leq x \leq 60$ , for which

$gcd(7x+n-1,n)=1 \ \forall \ 2 \leq n \leq 301$

equivalently

$gcd(7x-1,n)=1 \ \forall \ 2 \leq n \leq 301$

If $1 \leq x \leq 43$ , then $6 \leq 7x-1 < 301$ . Therefore, there would definitely be a $2 \leq n \leq 301$ such that $gcd(7x-1,n) \neq 1$ (just take $n=7x-1$ ).

If $44 \leq x \leq 60$ , then $307 \leq 7x-1 \leq 419$ is either a prime or it has a non-trivial factor that is less than or equal to $301$ . If $307 \leq 7x-1 \leq 419$ has a factor less that $301$ , then there is a $2 \leq n \leq 301$ such that $gcd(7x-1,n) \neq 1$ . If $307 \leq 7x-1 \leq 419$ is a prime, then $gcd(7x-1,n)=1 \ \forall \ 2 \leq n \leq 301$ . Therefore, we need to find all the primes in the interval $[307,419]$ , such that they are $6$ , modulo $7$ .there would be $19$ primes to check and only $3$ of them ( $307,349,419$ ) satisfy the conditions.

Count number

1 solution

0 pending reports