# Let $a,b \in \Bbb Z$, $p$ a prime and $p \gt 2$, given the following

Let $a\in \Bbb Z$, $b\in \Bbb Z$ such that $p \nmid b$, and $p$ a prime where $p \gt 2$.

If for all $x \in \Bbb Z$ such that $p \nmid x$ and $\operatorname{ord}_p(x) \ne p-1$, $p$ satisfies $\operatorname{ord}_p(a+bx) = p-1$, prove that $p$ is in the form:

$p = 2^{2^n} + 1$ for some $n$ non-negative.

-
What did you try? – Rasmus Oct 28 '12 at 23:35
The problem is difficult to read. It is not true that for all $x$, $p$ does not divide $x$. So you want to say that for all $x$ such that $p$ does not divide $x$, something happens. – André Nicolas Oct 28 '12 at 23:58
I have rephrased the problem, thank you for your suggestion. @AndréNicolas – fmat Oct 29 '12 at 0:52
What does ${\cal O}_p$ mean? – Gerry Myerson Oct 29 '12 at 0:57
the order modulo $p$, so for instance $\mathcal O_p(x)=3$ means $d=3$ is the least positive integer s.t. $x^d \equiv 1 \pmod p$. – fmat Oct 29 '12 at 1:29

Remark that there are $p-1 - \phi(p-1)$ elements of order not $p-1$ modulo $p$ because there are $\phi(p-1)$ elements of order $p-1$. We can pick $p-1 - \phi(p-1)$ values of $b$ which satisfy the conditions and thus it follows there are at least $p-1 - \phi(p-1)$ distinct elements of order $p-1$. But then: $$p-1 - \phi(p-1) \le \phi(p-1)$$ However, this implies $p-1 \le 2\phi(p-1)$. But as $2|(p-1)$ it follows $\phi(p-1) \le \frac{p-1}{2}$ on inequality iff $p-1$ is a power of two. It immediately follows $p = 2^n + 1$ for some $n$ and thus we are done.
Your first sentence is prima facie self-contradictory. Did you leave out a "not"? Also, I think you'll find $\phi(7-1)\le(7-1)/2$ even though $7-1$ is not a power of two. – Gerry Myerson Oct 29 '12 at 12:06
Yes, sorry I left out the word "not" accidentally. And yes it is true that $\phi(7-1) \le (7-1)/2$, however what I am saying is that $\phi(p-1) = (p-1)/2$ would only occur when $p-1$ is a power of $2$. As I prove that $p-1 - \phi(p-1) \le \phi(p-1)$ it follows equality must occur, which gives us the desired result. – dinoboy Oct 29 '12 at 16:38
But $p-1-\phi(p-1)\le\phi(p-1)$ is false for $p=7$ (and many other primes not of the form $2^{2^n}+1$). – Gerry Myerson Oct 29 '12 at 23:28
That's the point, that's where the contradiction is derived to show $p$ must be of that form! – dinoboy Oct 30 '12 at 0:31
@dinoboy good but you might also have to prove that the some $n$ that you have has to be a power of 2, i.e. $n=2^m$ for some $m \in\Bbb N$? – fmat Oct 31 '12 at 0:40