For which positive integers $n$ does there exist a positive integer $m$ for which all numbers between $mn$ and $(m+1)n$ coprime to $n$ are prime?

61 Views Asked by At

For which positive integers $n$ does there exist a positive integer $m$ for which all $\varphi(n)$ numbers between $mn$ and $(m+1)n$ coprime to $n$ are prime?

I think that there are only finitely many such integers $n$.

Trivially, $1$ and $2$ work. However, $3$ does not work, because one of $3m+1$ and $3m+2$ must be an even number $>2$. In fact, no odd number $>1$ works for $n$ for the same reason.

If $n=4$, then there are many $m$ for which $4m+1$ and $4m+3$ are a pair of twin primes, such as $m=1$ (giving the pair $5,7$) and $m=4$ (giving the pair $17,19$).

If $n=6$, then there are many $m$ for which $6m+1$ and $6m+5$ are a pair of cousin primes, such as $m=1$ (giving the pair $7,11$) and $m=2$ (giving the pair $13,17$).

If $n=8$ or any higher power of $2$, then at least one of the $\frac{n}{2}$ odd numbers between $mn$ and $(m+1)n$ must be divisible by $3$ and hence not prime. So, $8$ and higher powers of $2$ do not work for $n$.

If $n=10$, then there are many $m$ for which $10m+d$ (ending with the digit $d$ in decimal) is prime for all $d \in \{1,3,7,9\}$, such as $m=1$ (giving $11,13,17,19$) and $m=10$ (giving $101,103,107,109$).

If $n=12$, then there are many $m$ for which $12m+d$ (ending with the digit $d$ in duodecimal) is prime for all $d \in \{1,5,7,11\}$, such as $m=1$ (giving $13,17,19,23$) and $m=3$ (giving $37,41,43,47$).

If $n=14$ or any larger even number that is not divisible by $3$ or $5$, then one of $mn+1, mn+3, mn+5$ must be divisible by $3$ and hence not prime. So, $14$ does not work for $n$, nor does any larger even number that is not divisible by $3$ or $5$.

The case $n=18$ is a bit trickier. Could $18m+1,18m+5,18m+7,18m+11,18m+13,$ and $18m+17$ all be prime? If so, then none of them could be divisible by $5$, which could happen only if $m \equiv 2 \pmod{5}$. Also, none of them could be divisible by $7$, which could happen only if $m \equiv 3 \pmod{7}$. So, $m \equiv 17 \pmod{35}$ by the Chinese remainder theorem. Unfortunately, $m=17$ will not work, because $18(17)+17$ is clearly divisible by $17$. So, let's try $m=52$. In this case, $18(52)+13=949$ is divisible by $13$, while $18(52)+7=943$ is divisible by $23$, so they are both not prime. Trying larger values of $m$ will still give at least one composite number, until we get to $m=892$ when we finally get all primes ($16057,16061,16063,16067,16069,$ and $16073$). So, $18$ actually works for $n$ (but it requires a large $m$ to get all primes).

If $n=20$ or any larger number with prime factors $2$ and $5$ only, then at least one of the $\frac{2n}{5}$ numbers between $mn$ and $(m+1)n$ ending with $1,3,7,$ or $9$ must be divisible by $3$ and hence not prime. So, numbers $\ge 20$ of the form $2^k \cdot 5^l$ with $k$ and $l$ both positive integers do not work for $n$.

If $n=24$ or any larger number with prime factors $2$ and $3$ only, then at least one of the $\frac{n}{3}$ numbers between $mn$ and $(m+1)n$ coprime to $n$ must be divisible by $5$ and hence not prime. So, numbers $\ge 24$ of the form $2^k \cdot 3^l$ with $k$ and $l$ both positive integers do not work for $n$.

If $n=30$, then for at least one $d \in \{1,7,11,13,17,19,23,29\}$, $30m+d$ must be divisible by $7$ and hence not prime. So, $30$ does not work for $n$, nor does any larger number with prime factors $2,3,$ and $5$ only.

In fact, I think that the only values for $n$ that work are those $n \in \{1,2,4,6,10,12,18\}$.