Reasoning about $x(x+2)$ relatively prime to $\dfrac{p\#}{w}$

54 Views Asked by At

Let:

  • $p_k$ be the $k$th prime so that $p_3 = 5$
  • $p\#$ be the primorial of $p$.
  • $\text{gcd}(a,b)$ be the greatest common divisor of integer $a$ and integer $b$.
  • $w \ge 1$ be an integer that divides $p\#$

Does it follow that for all integers $k \ge 3$ and all integers $m$, there exists an integer $x$ where:

  • $m < x \le m + \dfrac{p_k\#}{w}$
  • $\text{gcd}\left(x[x+2],\dfrac{p_k\#}{w}\right)=1$

Here is the inductive argument:

(1) Base Case: $k=3$

For $p=p_3=5$ where $p\# = 30$, we need only consider $w \in \{1,2,3,5,6,10,15,30\}$

  • For $w=30$, $x=m+1$.
  • For $w=15$, $x = m + 1 + c$ where $m \equiv c \pmod 2$.
  • For $w=10$, $x = m + 1 + \dfrac{c^3-3c+2}{2}$ where $m \equiv c \pmod 3$
  • For $w =6$, $x = m + 2 - d$ where $m \equiv c \pmod 5$ and $c \equiv d \pmod 2$
  • For $w = 5$, if $c < 5$, $x = m + 5 - c$ else $x = m+6$ where $m \equiv c \pmod 6$
  • For $w = 3$, if $c < 7$, $x = m + 7 - c$ else $x = m + 11 - c$ where $m \equiv c \pmod {10}$
  • For $w = 2$, if $c < 11$, $x = m + 11 - c$ else $x = m + 17 - c$ where $m \equiv c \pmod {15}$
  • For $w = 1$, if $c < 29$, $x = m + 29 - c$ else $x = m + 30$ where $m \equiv c \pmod {30}$

(2) Assume up to some $k \ge 3$, for all integer $m, w | p_k\#$, there exists $x$ where $m < x \le m + \dfrac{p_k\#}{w}$ and $\text{gcd}\left(x[x+2],\dfrac{p_k\#}{w}\right)=1$

(3) For all $m,w | p_{k+1}\#$, there exists $x$ where $m < x \le m + \dfrac{p_{k+1}\#}{w}$ and $\text{gcd}\left(x[x+2],\dfrac{p_{k+1}\#}{w}\right)=1$

  • If $w$ divides $p_k\#$:
  • There exists $x_1, x_2, \dots x_{p_{k+1}}$ where $m+(i-1)\dfrac{p_k\#}{w} < x_i \le m+i\dfrac{p_k\#}{w}$ from step (2).

  • Now, $x_1, x_1+\dfrac{p_k\#}{w}, \dots, x_1+(p_{k+1}-1)\dfrac{p_k\#}{w}$ and $x_1+2, x_1+2 + \dfrac{p_k\#}{w}, \dots, x_1+2 + (p_{k+1}-1)\dfrac{p_k\#}{w}$ form complete residue systems modulo $p_{k+1}$.

  • So, it follows that at most two of $x_1, \dots x_{p_{k+1}}$ don't have the property where $m < x_i \le m + \dfrac{p_{k+1}\#}{w}$ and $\text{gcd}\left(x[x+2],\dfrac{p_{k+1}\#}{w}\right)$

  • If $w$ does not divide $p_k\#$:
  • In this case, $p_{k+1}$ divides $w$ and there exists $w' = \dfrac{w}{p_{k+1}}$ such that $\dfrac{p_{k+1}\#}{w} = \dfrac{p_k\#}{w'}$

  • In this case, the $x$ that solves for $\dfrac{p_k\#}{w'}$ also solves for $\dfrac{p_{k+1}\#}{w}$

Is this argument valid? Did I make a mistake?

1

There are 1 best solutions below

2
On BEST ANSWER

We can solve for any integer $A$, not just for primorial divided by something, and proof is clearly easier.

Here, we should state that, for any positive number $m$, there is a number $x$ in $[m, m+A)$ which $gcd(x(x+2), A) = 1$.

The necessary/sufficient condition for $gcd(x(x+2), A) = 1$ is, $gcd(x, A)=1$ and $gcd(x+2, A) = 1$.

It is obvious that the GCD will be $1$ when $x \ mod \ A = A - 1$, because $(x+2) \ mod \ A = 1$ will also hold, and it is clear that both GCD is $1$.

Additionally, for any positive number $m$, there is a number $x$ in $[m, m+A)$ that $x \ mod \ A = A-1$, because all possible $x \ mod \ A$ will appear in $[m, m+A)$.