# Number theory in sequence $x_{n+1}=x_n^3-2x_n^2+2$

$$x_1=5, x_{n+1}=x_n^3-2x_n^2+2$$ Prove that, there is no prime $$p=4k+3(k>1)$$ and $$p\mid x_n^2-3x_n+3$$

I think I can have $$p\mid t^2+1$$ and then I have QED.

But $$p\mid x_n^2-3x_n+3$$ means that $$p\mid (2x_n-3)^2+3=t^2+3$$

What should I do next?

• $x_n^3-3x_n^2+2=(x_n+1)(x_n^2-3x_n+3)-1$, may be if we prove $p|x_n^3-3x_n^2+2$ then problem is solved. Commented Dec 4, 2020 at 16:15
• where did you get the problem? Commented Dec 4, 2020 at 17:51

## 1 Answer

I found this to be a quite interesting (and challenging to solve) question. It's asking about the primes $$p$$ where

$$p \mid x_n^2 - 3x_n + 3 \tag{1}\label{eq1A}$$

As you showed, multiplying by $$4$$ gives

$$p \mid 4x_n^2 - 12x_n + 12 = (2x_n - 3)^2 + 3 \tag{2}\label{eq2A}$$

Since $$p \neq 3$$ (note $$x_n \equiv 5 \pmod{72}$$ for all $$n \ge 1$$, with this giving $$x_n^2 - 3x_n + 3 \equiv 13 \pmod{72}$$), this shows $$-3$$ is a quadratic residue modulo $$p$$.

Next, multiplying \eqref{eq1A} by $$x_n - 3$$ gives

\begin{aligned} (x_n - 3)(x_n^2 - 3x_n + 3) & = x_n^3 - 3x_n^2 + 3x_n - 3x_n^2 + 9x_n - 9 \\ & = x_n^3 - 6x_n^2 + 12x_n - 8 - 1 \\ & = (x_n - 2)^3 - 1 \end{aligned}\tag{3}\label{eq3A}

This means

$$(x_n - 2)^3 \equiv 1 \pmod{p} \tag{4}\label{eq4A}$$

If $$n \gt 1$$, substituting $$x_n = x_{n-1}^3 - 2x_{n-1}^2 + 2$$ gives

\begin{aligned} (x_{n-1}^3 - 2x_{n-1}^2)^3 & \equiv (x_{n-1}^2(x_{n-1} - 2))^3 \\ & \equiv x_{n-1}^6(x_{n-1} - 2)^3 \\ & \equiv 1 \pmod{p} \end{aligned}\tag{5}\label{eq5A}

Repeating the substitutions for each $$x_i - 2 = x_{i-1}^2(x_{i-1} - 2)$$ for $$i$$ from $$n - 1$$ down to $$2$$ gives a product of $$0$$ or more $$x_{i-1}^6$$ values multiplied by $$(x_1 - 2)^3 = 3^3$$, i.e.,

$$\left(\prod_{i=1}^{n-1}x_i\right)^6(3^3) \equiv 1 \pmod{p} \tag{6}\label{eq6A}$$

Multiplying both sides by $$3$$ gives

$$\left(\left(\prod_{i=1}^{n-1}x_i\right)^3 3^2\right)^2 \equiv 3 \pmod{p} \tag{7}\label{eq7A}$$

This shows $$3$$ is also a quadratic residue. Thus, $$3^{-1}(-3) \equiv -1 \pmod{p}$$ is a quadratic residue, so there's an integer $$x$$ with $$x^2 \equiv -1 \pmod{p} \implies x^4 \equiv 1 \pmod{p}$$. Therefore, $$4$$ is the multiplicative order of $$x$$ modulo $$p$$, so $$4 \mid p -1 \implies p \equiv 1 \pmod{4}$$. This proves that $$p$$ cannot be of the form $$4k + 3$$.

• Wait...I am still not seeing how you went from (5) to (6)....
– Mike
Commented Dec 7, 2020 at 18:37
• @Mike If $n \gt 2$, then by definition, $x_{n-1} = x_{n-2}^3 - 2x_{n-2}^2 + 2$, so $x_{n-1} - 2 = x_{n-2}^3 - 2x_{n-2}^2$. Substituting into $(5)$ gives $x_{n-1}^6(x_{n-2}^3 - 2x_{n-2}^2)^3 = x_{n-1}^6(x_{n-2}^2(x_{n-2} - 2))^3 = x_{n-1}^6x_{n-2}^6(x_{n-2} - 2)^3$. At each step, there's an extra $x_i^6$ factor with a smaller index $i$, plus for the same $i$ (with it being $n-2$ at this step) being the factor of $(x_i-2)^3$. Repeating this substitution for each smaller index down to $2$ (so have $(x_1-2)^3$ on right), then using product notation & putting power of $6$ around it gives my $(6)$. Commented Dec 7, 2020 at 18:44
• OR..should (5) be $\ldots \equiv x^6_{n-1}(x_{n-1}-2)^3 \ldots$ i.e., $(x_{n-1}-2)^3$ instead of $(x_{n-1}-2)$? If so then I can follow the rest of this proof...very nice
– Mike
Commented Dec 7, 2020 at 19:07
• @Mike You're right that $(5)$ should be $x_{n-1}^6(x_{n-1}-2)^3$ instead. As you can see, I've just updated my answer to correct that mistake. Thanks for pointing this out and I'm sorry for the trouble & confusion it caused you. Commented Dec 7, 2020 at 19:08
• It is a beautiful proof to what looks like quite a challenging problem! I wanted to be able to follow it
– Mike
Commented Dec 7, 2020 at 19:13