5
$\begingroup$

$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?

$\endgroup$
2
  • $\begingroup$ $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. $\endgroup$
    – sirous
    Commented Dec 4, 2020 at 16:15
  • 5
    $\begingroup$ where did you get the problem? $\endgroup$
    – Will Jagy
    Commented Dec 4, 2020 at 17:51

1 Answer 1

5
$\begingroup$

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{equation}\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}\end{equation}\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{equation}\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}\end{equation}\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$.

$\endgroup$
10
  • 1
    $\begingroup$ Wait...I am still not seeing how you went from (5) to (6).... $\endgroup$
    – Mike
    Commented Dec 7, 2020 at 18:37
  • 1
    $\begingroup$ @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)$. $\endgroup$ Commented Dec 7, 2020 at 18:44
  • 2
    $\begingroup$ 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 $\endgroup$
    – Mike
    Commented Dec 7, 2020 at 19:07
  • 2
    $\begingroup$ @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. $\endgroup$ Commented Dec 7, 2020 at 19:08
  • 2
    $\begingroup$ It is a beautiful proof to what looks like quite a challenging problem! I wanted to be able to follow it $\endgroup$
    – Mike
    Commented Dec 7, 2020 at 19:13

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .