0
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ @ThomasAndrews Yes. Note that the reference solution uses $q$ as in $f_{q-1}$ $\endgroup$
    – Lily White
    Aug 12, 2022 at 3:23
  • $\begingroup$ The question doesn't apparently have anything to do with Fibonacci, but that doesn't mean the answer can't. $\endgroup$
    – Thomas Andrews
    Aug 12, 2022 at 3:34
  • 5
    $\begingroup$ 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. $\endgroup$
    – Thomas Andrews
    Aug 12, 2022 at 3:39
  • $\begingroup$ This looks like a contest problem. Would you mind giving a source? $\endgroup$
    – Aphelli
    Aug 12, 2022 at 6:06
  • $\begingroup$ @Aphelli It's a training problem from Mid-level Mathematics (中等数学). ISBN 978-7-5603-9943-0 $\endgroup$
    – Lily White
    Aug 12, 2022 at 6:28

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .