2
$\begingroup$

During my research, I come across this question.

Let $p=3^{101}-4$, $x_0=0$ and $x_{n+1}=x_n^3+1 \mod p$.

Is it true that $\exists k \in \mathbb N \cap [3,p-2], x_k=1$ ?

I have posted this question here : https://artofproblemsolving.com/community/c6h3213569

Improve this question
$\endgroup$

1 Answer 1

Reset to default
7
$\begingroup$

Since $p$ is prime and $\left(\frac{-3}p\right)=-1$, the function $f(x) := x^3 +1$ has the unique inverse and thus represents a permutation on $\mathbb Z/p\mathbb Z$. This means that starting at $x_1=1$ iterative application of $f$ should yield $1$ again. The number of iterations equals the length of the cycle to which $1$ belongs in the permutation $f$.

It remains to notice that $f$ has one fixed point and one cycle of length 3 as established by this PARI/GP code. It follows that the cycle of element 1 has length $\leq p-4$ giving $k$ in the desired interval.

Btw, the inverse of $f$ can be stated explicitly as $f^{-1}(y)=(y-1)^{2\cdot 3^{100}-3}$.

Improve this answer
$\endgroup$
13
  • $\begingroup$ So the answer is yes or no ? $\endgroup$
    – Dattier
    Commented Feb 4 at 13:28
  • 1
    $\begingroup$ Nice. Btw the same code says that $f^{\circ k}$ has only 1 or 4 fixed points for $k\le 9$, namely 4 iff $3|k$. Thus I don't know if the cycle containing zero has length $p-4$ (which would imply that $f^{\circ (p-3)}(0)=1$). $\endgroup$
    – YCor
    Commented Feb 4 at 14:22
  • 4
    $\begingroup$ @Dattier well, comments is probably not the right place to do so. $\endgroup$
    – YCor
    Commented Feb 4 at 15:00
  • 2
    $\begingroup$ MathOverflow is not intended for challenges. $\endgroup$
    – Gerry Myerson
    Commented Feb 4 at 21:08
  • 1
    $\begingroup$ @YCor: I've confirmed that there are no other cycles of length $\leq 12$. $\endgroup$
    – Max Alekseyev
    Commented Feb 5 at 14:07

You must log in to answer this question.

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