Problem A. 909. (May 2025)

A. 909. Prove that for any positive integer $\displaystyle N$, there exists a positive integer $\displaystyle n>2$ such that the difference between any two distinct prime factors of $\displaystyle n^3-1$ is at least $\displaystyle N$.

(7 pont)

Deadline expired on June 10, 2025.

We know that $\displaystyle n^3-1=(n-1)(n^2+n+1)$. Let $\displaystyle n=m+1$, then the second factor can be rewritten as $\displaystyle m^2+3m+3$. Now note that

$$\begin{align*} (m^2-3m+3)(m^2+3m+3)&=m^4-3m^2+9\\ (m^2+3)(m^4-3m^2+9)&=m^6+27\\ (m^6+27)(m^6-27)&=m^{12}-3^6, \end{align*}$$

therefore if $\displaystyle p\neq 3$ divides $\displaystyle m^2+3m+3$, then $\displaystyle m^{12}\equiv 3^6$ mod $\displaystyle p$. Let's choose $\displaystyle m$ to be a power of 3: $\displaystyle m=3^\alpha$, then $\displaystyle 3^{12\alpha} \equiv 3^6$ mod $\displaystyle p$, end therefore $\displaystyle d|12\alpha-6=6(2\alpha-1)$. Now let's choose $\displaystyle 2\alpha-1$ also as a power of 3, so let $\displaystyle 2\alpha-1=3^\beta$. Then $\displaystyle d|2\cdot 3^{\beta+1}$, thus $\displaystyle d=3^\gamma$ or $\displaystyle d=2\cdot 3^\gamma$ for some $\displaystyle \gamma\le \beta+1$. We will prove that $\displaystyle \gamma=\beta+1$. Let's assume for the sake of contradiction that $\displaystyle \gamma\le \beta$.

Case 1. If $\displaystyle d=3^\gamma$, then $\displaystyle d|2\alpha-1$, so $\displaystyle 3^{2\alpha-1}\equiv 1$ mod $\displaystyle p$. Therefore

$\displaystyle m^2+3m+3=3^{2\alpha}+3^{\alpha+1}+3\equiv 3+3^{\alpha+1}+3\equiv 3\cdot(3^\alpha+2)\,\text{mod}\,p, $

so $\displaystyle 3^{\alpha}\equiv -2$ mod $\displaystyle p$. However, this implies $\displaystyle 3^{2\alpha}\equiv 4$ mod $\displaystyle p$, which contradicts $\displaystyle 3^{2\alpha-1}\equiv 1$ mod $\displaystyle p$ (which implies $\displaystyle 3^{2\alpha}\equiv 3$ mod $\displaystyle p$.

Case 2. If $\displaystyle d=2\cdot 3^\gamma$, then $\displaystyle 3^d-1=(3^{d/2}-1)(3^{d/2}+1)$, and $\displaystyle p$ cannot divide the first factor by the definition of the order, therefore it divides the second factor. This implies $\displaystyle 3^{3^\gamma}\equiv 3^{d/2}\equiv -1$ mod $\displaystyle p$. Since $\displaystyle 3^{2\alpha-1}=3^{3^\beta}$ is an odd power of $\displaystyle 3^{3^\gamma}$, it's also -1 mod $\displaystyle p$. Thus

$\displaystyle m^2+3m+3=3^{2\alpha}+3^{\alpha+1}+3\equiv -3+3^{\alpha+1}+3\equiv 3^{\alpha+1}\,\text{mod}\,p, $

which is a contradiction.

Thus $\displaystyle 3^{\beta+1}$ must divide $\displaystyle d$, which divides $\displaystyle p-1$ because of Fermat's little theorem. So we have proved that every prime factor different from 3 must be 1 modulo $\displaystyle 3^{\beta+1}$, so any two prime factors of $\displaystyle n^3-1$ must differ by at least $\displaystyle 3^{\beta}-2$, which finishes our proof, since $\displaystyle \beta$ can be chosen arbitrarily.

Statistics:

8 students sent a solution.

7 points: Bodor Mátyás, Forrai Boldizsár, Tianyue DAI, Varga Boldizsár, Xiaoyi Mo.

0 point: 3 students.

Problems in Mathematics of KöMaL, May 2025

8 students sent a solution.
7 points:	Bodor Mátyás, Forrai Boldizsár, Tianyue DAI, Varga Boldizsár, Xiaoyi Mo.
0 point:	3 students.

Already signed up?
New to KöMaL?