# Existence of prime $p$ and integer $x$ satisfying $x^{q-1}-x+1\equiv 0\pmod p, x^q\equiv 1 \pmod p$ for all odd $q\ge 7$

As the title suggests, the problem is to determine whether there exists, for all odd $$q \ge 7$$, a prime $$p$$ and integer $$x$$, such that $$x^{q-1}-x+1\equiv 0\pmod p,$$ $$x^q\equiv 1 \pmod p$$

The official solution is weird to me. It first proves a lemma that for all odd $$q \ge 5$$, $$f_{q-1}+f_{q+1}$$ is not a power of $$2$$, where $$f_x$$ is the fibonacci number. Then, it chooses $$p$$ as an odd prime factor of $$f_{q+1}+f_ {q-1}$$ and $$x = \frac{p+1}2(5f_{q+1}+1)$$

Now, the solution itself is fairly written. (It's in Chinese, the gist is all summarized above) But I really can't see what this problem has got to do with Fibonacci numbers. I'm also wondering if there exists a non-constructive proof.

• @ThomasAndrews Yes. Note that the reference solution uses $q$ as in $f_{q-1}$ Aug 12, 2022 at 3:23
• The question doesn't apparently have anything to do with Fibonacci, but that doesn't mean the answer can't. Aug 12, 2022 at 3:34
• Given that $x^{q-1}-x+1$ and $x^{q}-1$ are both divisible by $p,$ then $$x^q-1-x(x^{q-1}-x+1)=x^2-x-1$$ is divisible by $p.$ So you need $x^q-1$ and $x^2-x-1$ both divisible by $p.$ And $x^2-x-1$ definitely has something to do with Fibonacci. Aug 12, 2022 at 3:39
• This looks like a contest problem. Would you mind giving a source? Aug 12, 2022 at 6:06
• @Aphelli It's a training problem from Mid-level Mathematics (中等数学). ISBN 978-7-5603-9943-0 Aug 12, 2022 at 6:28