Smallest integer N such that among every ten consecutive larger integers is at least one having at least three distinct prime factors?

The problem is:

There exists an integer $N$ such that for any $n>N$, there exists $m \in \{n,n+1, \ldots ,n+9\}$ such that $m$ has at least $3$ distinct prime factors.

2 Years ago, My professor said to me it could be solved by using elementary number theory.

I considered this problem for 1 week. But I couldn't solve this problem. But professor didn't answer.

P.S I was considered about multiple of 6 2years ago. But it is not simple.

Solution 1:

I probably have most of it, maybe someone else will know how to finish it. I think you can do this by considering only the primes 2,3,5, in any detail.

You have, in particular, five consecutive even numbers. At least one of those is divisible by 3 as well. Unless this is the middle of five, there is another one divisible by 3. In which case you have, assuming at most two distinct prime factors, $ 2^a 3^b - 2^c 3^d = \pm 6. $ So one of $a,c$ is one, and one of $b,d$ is one. The possibilities are $2^\alpha 3^\beta - 1 = \pm 1$ or $2^\alpha - 3^\beta = \pm 1.$ Quite finite, by Catalan.

Alright, so now the middle even number is also divisible by 3. One of the five even numbers is divisible by 5. Not the same one, that would make three prime factors. So we get $$ 2^a 3^b - 2^c 5^d \in \{ \pm 2, \pm 4. \} $$ Divide by the gcd which is 2 or 4, we get $$ 3^\beta - 2^\gamma 5^\delta = \pm 1, $$ $$ 5^\delta - 2^\gamma 3^\beta = \pm 1. $$ The largest solution to any of the four equations summarized above, that I find, is $81 - 80 = 1,$ and I imagine this can be proved. Multiplying back by 2 or 4, the biggest original would be $324 - 320 = 4.$

So, if the middle even number is at least $324 + 6 = 330,$ so your $n$ is at least 325, the equations above do not have solutions, and so either the $2^a 3^b$ or the $2^c 5^d$ term has at least a third prime factor.

Solution 2:

Indeed, it can be solved using only elementary number theory. My solution is a bit long though, and it may be possible to simplify it.

In the following proof, I will use the following result, which will be proved at the end:

Proposition: The following equations have finitely many non-negative integer solutions:

\begin{align} 1) & 2^a-3^b=1 \\ 2) & 3^b-2^a=1 \\ 3) & 2^a3^b-5^d=1 \\ 4) & 5^d-2^a3^b=1 \\ 5) & 3^b-2^c5^d=1 \\ 6) & 2^c5^d-3^b=1 \\ 7) & 3^b-5^d=2 \\ 8) & 5^d-3^b=2 \end{align}

Each of these equations can easily be solved using only modular arithmetic. Suppose for now that the above proposition is true, and suppose any integer solution has $a, b, c, d$ bounded by $P \geq 1$ from above. (In fact, as we shall see later at the end, we can have $P=4$.) Choose $N>6(6)^P$.

Take $n>N$ and assume on the contrary that each of $n, n+1, \ldots , n+9$ has $\leq 2$ distinct prime factors. There are exactly $5$ even numbers $2m, 2(m+1), 2(m+2), 2(m+3), 2(m+4)$ among these 10 consecutive numbers, so each of $m, m+1, m+2, m+3, m+4$ must be of the form $2^ap^k$. (The odd part must be a prime power) Note that $2m \geq n>N>6(6^P)$, so $m>3(6^P)$.

If $m \equiv 0 \pmod{3}$, then both $m$ and $m+3$ are divisible by $3$, so exactly one of $\frac{m}{3}$ and $\frac{m+3}{3}=\frac{m}{3}+1$ is divisible by $3$. Thus one of $\frac{m}{3}$ and $\frac{m}{3}+1$ is a power of $2$, and the other is a power of $3$. This gives $2^a-3^b= \pm 1$, which corresponds to equations $1, 2$ of the proposition. This implies that $m$ is either $3(2^a)$ or $3(3^b)$, and in any case, $3(6^P)<m \leq 3(3^P)$, a contradiction.

Similarly, if $m \equiv 2 \pmod{3}$, then one of $\frac{m+1}{3}$ and $\frac{m+1}{3}+1$ is a power of $2$, and the other is a power of $3$, and again we get $2^a-3^b= \pm 1$, which corresponds to equations $1, 2$ of the proposition. Similarly $m+1$ is either $3(2^a)$ or $3(3^b)$, and in any case, $3(6^P)+1<m+1 \leq 3(3^P)$, a contradiction.

Therefore $m \equiv 1 \pmod{3}$. This implies that $m+2$ is divisible by $3$, so let $m+2=2^a3^b$ for some non-negative integers $a, b$. Then exactly one of $m, m+1, m+3, m+4$ is a multiple of $5$ and thus equal to $2^c5^d$. Therefore $2^a3^b-2^c5^d= \pm 1, \pm 2$.

If $2^a3^b-2^c5^d=\pm 1$, then clearly $a, c$ cannot be both $\geq 1$, so at least one of them is $0$. If $a=0$, we get $3^b-2^c5^d=\pm 1$, which corresponds to equations $5, 6$ of the proposition. This implies that $3(10^P)+2<m+2=3^b \leq 3^P$, a contradiction. If $c=0$, then we get $2^a3^b-5^d= \pm 1$, which corresponds to equations $3, 4$ of the proposition. This implies that $3(6^P)+2<m+2=2^a3^b \leq 6^P$, a contradiction.

Therefore $2^a3^b-2^c5^d=\pm 2$. If $a, c \geq 1$, then $2^{a-1}3^b-2^{c-1}5^d=\pm 1$. As above, $a-1, c-1$ cannot be both $\geq 1$, so at least one of them is $0$. If $a-1=0$, then we get $3^b-2^{c-1}5^d=\pm 1$, which corresponds to equations $5, 6$ of the proposition. This implies that $3(6^P)+2<m+2=2(3^b) \leq 2(3^P)$, a contradiction. If $c-1=0$, then we get $2^{a-1}3^b-5^d= \pm 1$, which corresponds to equations $3, 4$ of the proposition. This implies that $3(6^P)+2<m+2=2^a3^b \leq 2(6^P)$, a contradiction.

Therefore at least one of $a, c$ is $0$. If $a=0$, then $3^b-2^c5^d=\pm 2$, so $2 \nmid 2^c5^d$, so $c=0$. Similarly if $c=0$, then $2^a3^b-5^d=\pm 2$, so $2 \nmid 2^a3^b$, so $a=0$. Thus $a=c=0$, and we get $3^b-5^d=\pm 2$, which corresponds to equations $7, 8$ of the proposition. Thus $3(6^P)+2<m+2=3^b \leq 3^P$, a contradiction.

Therefore for $n>N$, there exists $m \in \{n, n+1, n+2, \ldots , n+9\}$ s.t. $m$ has $\geq 3$ prime factors.

Proof of Proposition:

We shall go 1 step further; we shall find all non-negative integer solutions.

\begin{align} 1) & 2^a-3^b=1 \end{align}

If $b=0$, then $a=1$. Otherwise $b \geq 1$. Taking $\pmod{3}$ gives $2^a \equiv 1 \pmod{3}$, so $a$ is even. Thus $3^b=2^a-1=(2^{\frac{a}{2}}-1)(2^{\frac{a}{2}}+1)$. Since $\gcd(2^{\frac{a}{2}}-1, 2^{\frac{a}{2}}+1)=1$ and $1 \leq 2^{\frac{a}{2}}-1<2^{\frac{a}{2}}+1)$, we have $2^{\frac{a}{2}}-1=1$, so $a=2$, giving $b=1$.

We thus have the solutions $(a, b)=(1, 0), (2, 1)$.

\begin{align} 2) & 3^b-2^a=1 \end{align}

If $a=0$, then $3^b=2$, a contradiction. If $a=1$, then $3^b=3$, so $b=1$. Otherwise $a \geq 2$. Taking $\pmod{4}$, $3^b \equiv 1 \pmod{4}$, so $b$ is even.

Thus $2^a=3^b-1=(3^{\frac{b}{2}}-1)(3^{\frac{b}{2}}+1)$. Note that $\gcd(3^{\frac{b}{2}}-1,3^{\frac{b}{2}}+1)=2$, so exactly one of $3^{\frac{b}{2}}-1$ and $3^{\frac{b}{2}}+1$ is equal to $2$. If $3^{\frac{b}{2}}+1=2$, then $3^{\frac{b}{2}}-1=0$, so $2^a=0$, a contradiction. Thus $3^{\frac{b}{2}}-1=2$, so $b=2$, giving $a=3$.

We thus have the solutions $(a, b)=(1, 1), (3, 2)$.

\begin{align} 3) & 2^a3^b-5^d=1 \end{align}

Taking $\pmod{4}$, $2^a3^b=5^d+1 \equiv 2 \pmod{4}$. Thus $a=1$, so $2(3^b)=5^d+1$. If $d=0$, then $b=0$. Otherwise $d \geq 1$. Taking $\pmod{5}$, we have $2(3^b) \equiv 1 \pmod{5}$, so $b \equiv 1 \pmod{4}$. Taking $\pmod{3}$, we have $5^d \equiv -1 \pmod{3}$ so $d$ is odd. This implies that $d \geq 1$, so $2(3^b)=5^d+1 \geq 5+1=6$, so $b \geq 1$. If $b=1$, then $d=1$. Otherwise $b \geq 2$, so taking $\pmod{9}$, we have $5^d \equiv -1 \pmod{9}$, so $d \equiv 3 \pmod{6}$. Thus taking $\pmod{7}$, $2(3^b)=5^d+1 \equiv 5^3+1 \equiv 0 \pmod{7}$, a contradiction.

We thus have the solutions $(a, b, d)=(1, 0, 0), (1, 1, 1)$.

\begin{align} 4) & 5^d-2^a3^b=1 \end{align}

Taking $\pmod{4}$, we have $2^a3^b \equiv 0 \pmod{4}$, so $a \geq 2$. If $b=0$, then $5^d-2^a=1$. Now if $a=2$, then $d=1$. Otherwise $a \geq 3$, so taking $\pmod{8}$, we have $5^d \equiv 1 \pmod{8}$, so $d$ is even. Thus $2^a=5^d-1=(5^{\frac{d}{2}}-1)(5^{\frac{d}{2}}+1)$. We have $5^{\frac{d}{2}}+1 \equiv 2 \pmod{4}$, so $5^{\frac{d}{2}}+1=2$, so $5^{\frac{d}{2}}-1=0$, so $2^a=0$, a contradiction.

Otherwise $b \geq 1$. Taking $\pmod{3}$, we have $5^d \equiv 1 \pmod{3}$, so $d$ is even. Thus $2^a3^b=5^d-1=(5^{\frac{d}{2}}-1)(5^{\frac{d}{2}}+1)$. Note that $\gcd(5^{\frac{d}{2}}-1, 5^{\frac{d}{2}}+1)=2$ and $5^{\frac{d}{2}}+1 \equiv 2 \pmod{4}$, so $5^{\frac{d}{2}}+1=2, 2(3^b)$.

If $5^{\frac{d}{2}}+1=2$, then $5^{\frac{d}{2}}-1=0$, so $2^a3^b=0$, a contradiction. Thus $5^{\frac{d}{2}}+1=2(3^b)$, and $5^{\frac{d}{2}}-1=2^{a-1}$. We have already shown above that the only non-negative integer solutions to $5^d-2^a=1$ is $(a, d)=(2, 1)$, so $\frac{d}{2}=1, a-1=2$, giving $d=2, a=3$. Thus $2(3^b)= 5^{\frac{d}{2}}+1=6$, so $b=1$.

We thus have the solutions $(a, b, d)=(2, 0, 1), (3, 1, 2)$.

\begin{align} 5) & 3^b-2^c5^d=1 \end{align}

If $d=0$, $3^b-2^c=1$, so by the above solution of equation $2$, we have $(c, b)=(1, 1), (3, 2)$. Otherwise $d \geq 1$.

Taking $\pmod{5}$, $3^b \equiv 1 \pmod{5}$, so $4 \mid b$. Thus $2^c5^d=3^b-1=(3^{\frac{b}{2}}-1)(3^{\frac{b}{2}}+1)$. Note that $\gcd(3^{\frac{b}{2}}-1,3^{\frac{b}{2}}+1)=2$ and $3^{\frac{b}{2}}+1 \equiv 2 \pmod{4}$. Thus $3^{\frac{b}{2}}+1=2, 2(5^d)$. If $3^{\frac{b}{2}}+1=2$, then $3^{\frac{b}{2}}-1=0$, so $2^c5^d=0$, a contradiction.

Thus $3^{\frac{b}{2}}+1=2(5^d), 3^{\frac{b}{2}}-1=2^{c-1}$. By the above solution of equation $2$, we have $(c-1, \frac{b}{2})=(1, 1), (3, 2)$. Since $4\mid b$, we cannot have $\frac{b}{2}=1$, so $\frac{b}{2}=2, c-1=3$. This gives $b=c=4$, so $2(5^d)=3^{\frac{b}{2}}+1=10$, giving $d=1$.

We thus have the solutions $(b, c, d)=(1, 1, 0), (2, 3, 0), (4, 4, 1)$.

\begin{align} 6) & 2^c5^d-3^b=1 \end{align}

If $d=0$, $2^c-3^b=1$, so by the above solution of equation $1$, we have $(c, b)=(1, 0), (2, 1)$. Otherwise $d \geq 1$. Taking $\pmod{5}$, $3^b \equiv 4 \pmod{5}$, so $b \equiv 2 \pmod{4}$. Thus $2^c5^d=3^b+1 \equiv 2 \pmod{4}$, so $c=1$. This gives $2(5^d)=3^b+1$. Since $b \equiv 2 \pmod{4}$, b \geq 2$.

Taking $\pmod{9}$, $2(5^d) \equiv 1 \pmod{9}$, so $d \equiv 1 \pmod{6}$. Taking $\pmod{7}$, $3^b=2(5^d)-1 \equiv 2(5)-1 \equiv 9 \pmod{7}$, so $b \equiv 2 \pmod{6}$.

If $b=2$, then $d=1$. Otherwise $b \geq 3$. Taking $\pmod{27}$, $2(5^d) \equiv 1 \pmod{27}$, so $d \equiv 7 \pmod{18}$. Now taking $\pmod{19}$ gives $3^b=2(5^d)-1 \equiv 2(5^7)-1 \equiv 12 \pmod{19}$, so $b \equiv 15 \pmod{18}$, a contradiction.

We thus have the solutions $(b, c, d)=(0, 1, 0), (1, 2, 0), (2, 1, 1)$.

\begin{align} 7) & 3^b-5^d=2 \end{align}

If $d=0$, then $b=1$. Otherwise $d \geq 1$. Taking $\pmod{5}$, $3^b \equiv 2 \pmod{5}$, so $b \equiv 3 \pmod{4}$. Taking $\pmod{16}$, we have $5^d=3^b-2 \equiv 3^3-2 \equiv 9 \pmod{16}$, so $d \equiv 2 \pmod{4}$. Thus $d \geq 2, b \geq 3$. Taking $\pmod{9}$, $5^d \equiv 7 \pmod{9}$, so $d \equiv 2 \pmod{6}$.

Taking $\pmod{7}$, we have $3^b=5^d+2 \equiv 5^2+2 \equiv 6 \pmod{7}$, so $b\equiv 3 \pmod{6}$. Taking $\pmod{27}$, $5^d \equiv 25 \pmod{27}$, so $d \equiv 2 \pmod{18}$. Taking $\pmod{19}$, we have $3^b=5^d+2 \equiv 5^2+2 \equiv 27 \pmod{19}$, so $b \equiv 3 \pmod{18}$.

Now if $b=3$, then $d=2$. Otherwise $b \geq 4$. Taking $\pmod{81}$, we have $5^d \equiv 79 \pmod{81}$, so $d \equiv 20 \pmod{54}$. Thus $d \equiv 74 \pmod{108}$. Taking $\pmod{109}$, we have $3^b=5^d+2 \equiv 5^{74}+2 \equiv 35+2 \equiv 37 \pmod{109}$. However, if we let $b=18k+3$, then we have $3^b \equiv 27(45^k) \equiv 16, 66, 27 \pmod{109}$, a contradiction.

We thus have the solutions $(b, d)=(1, 0), (3, 2)$.

\begin{align} 8) & 5^d-3^b=2 \end{align}

If $b=0$, then $5^d=3$, a contradiction. If $b=1$, then $d=1$. Otherwise $b \geq 2$, so $5^d=3^b+2 \geq 9+2$, so $d \geq 2$. Taking $\pmod{9}$, $5^d \equiv 2 \pmod{9}$, so $d \equiv 5 \pmod{6}$. Taking $\pmod{7}$, $3^b=5^d-2 \equiv 5^5-2 \equiv 1 \pmod{7}$, so $6 \mid b$. Taking $\pmod{5}$, $3^b \equiv 3 \pmod{5}$, so $b \equiv 1 \pmod{4}$, a contradiction.

We thus have the solution $(b, d)=(1, 1)$.