Reasoning about relatively prime factors of consecutive integers

Question

Let:

• $n,m,x$ be any integer with $n$ being even
• $D_n(m,x)$ be the count of integers $i$ where:

• $m-x \le i < m$
• There exists a prime $p \le x$ such that $p \nmid n$ but $p | i$

Examples:

$D_6(0,5) = 1$ { -5 } with $p=5$

$D_6(20,5) = 1$ { 15 } with $p=5$

I am trying to see whether it is always the case that:

$$D_n(m,x) \le D_n(0,x) + 1$$

I am having trouble either finding a counter example or finding the argument why it is true.

Intuitively, I would assume that it is not true. That there should exist $m,x,n$ such that $D_n(m,x) > D_n(0,x)+1$.

Answer 1

A counter example is $m = 22$, $n = 6$ and $x = 8$. In this case, $D_6(0,8) = 2$ since, for $-8 \le i \lt 0$, the only primes $p \le 8$ which don't divide $6$ are $5$ and $7$, but the values of $i$ that they do divide are just $-5$ and $-7$.

On the other hand, you have $D_6(22,8) = 4$ since checking $14 \le i \lt 22$ gives $5 \mid 15$ and $5 \mid 20$, plus $7 \mid 14$ and $7 \mid 21$.

Since $4 \gt 2 + 1$, this gives a case where $D_n(m,x) \gt D_n(0,x) + 1$ to show your condition does not always hold.

Answer 2

EDIT: I have the following counterexample in the comments (this one was incorrect): $n = 6$, $m = 50$, $x = 10$.

The counter-example I found was $m = 500$, $n = 2$ and $x = 10$. Here, $D_n(m,x) = 10$ and $D_n(0,x) \leq 8$ (since -8, -4, -2 are powers of 2 multiplied by $\pm 1$). This would violate the first inequality you state.

I include my thought process (to follow) as I noted in your bio you are a math enthusiast and aiming for grad school. Also, as I am the same, I thought it'd be for me a nice exercise.

My thought process was that if we take a really large $m$ and a small $x$, more numbers from the set $\{-x, \dots, -1\}$ would not be included in the count $D_n(0,x)$ compared to $D_n(m,x)$. For instance, in my example, for the quantity $D_n(m,x)$, one must only check that the numbers $490, \dots 499$ are not purely powers of 2. It is easy to generate counter-examples here in the sense that the gaps between successive powers of 2 (and any positive integer in general) gets very large very fast. Indeed, for the numbers of smaller absolute value in my example ($\{-10, \dots, -1\}$), there "is a greater chance" of there being powers of 2.