For a given integers $x,n$, counting the number of integers $v$ where $x < v \le x+n$ and gcd$(\frac{n}{4}\#,v)=1$

42 Views Asked by At

If $n < 188$, is it true for all integers $x,n$ that there exist at least $4$ integers $v$ such that $x < v \le x+n$ and gcd$(v,\frac{n}{4}\#)=1$?

I believe that the answer is yes. Here's my argument:

Lemma 1: For any integers $x,w,n$, there are at most $\left\lceil{\frac{n}{2w}}\right\rceil$ integers $v$ such that $x < v \le x+n$, $2 \nmid v$, $w | v$.

Argument:

Let $m=\lceil{\frac{n}{2w}}\rceil + 1$ so that $v_1, \dots v_m$ are all greater than $x$ and for each $v_i$, $2 \nmid v_i$ and $w | v_i$

Then: $v_m \ge v_i + (v_m - v_i) \ge x+1+2w(m-1) \ge x+1+ 2w(\frac{n}{2w}) \ge x + 1 + n$.

Lemma 2: For any integers $x,w,n$ where gcd$(w,6)=1$, there at least $\left\lfloor\frac{\lceil\frac{n}{2w}\rceil}{3}\right\rfloor$ integers $v$ where $x < v \le x+n, 2 \nmid w, (3w)|v$.

Argument:

Let $v_i,v_{i+1},v_{i+2}$ be any $3$ such $v$ so that $v_i = v_{i+1} - 2w = v_{i+2} - 4w$

$w \equiv 1 \pmod 3$ or $w \equiv 2 \pmod 3$ so that it follows that $v_i, v_{i+1},v_{i+2}$ are distinct congruence classes modulo $3$.

Claim: There are at least $4$ integers $v$ such that $x < v \le x+n$ and gcd$(v,\frac{n}{4}\#)=1$ for $4 \le n < 188$.

(1) Basis Step: Clearly true for $n \le 8$.

(2) If true for $n$ and $\frac{n+1}{4}$ is not a prime, then it is true for $n$.

The $4$ such $v$ between $x$ and $x+n$ are likewise relatively prime to $\lfloor\frac{n+1}{4}\rfloor\#$ since $\lfloor\frac{n}{4}\rfloor\# =\lfloor\frac{n+1}{4}\rfloor\#.$

(3) For $\frac{n}{4}$ in $\{3,5,7,11,13,17,19,23,29,31,37,41,43\}$, $n$ is even, there are $\frac{n}{2}$ odd primes, then using Lemma 1 and Lemma 2, it clear that in each case, there are $4$ or more left odd integers relatively prime to $\frac{n}{4}\#$.