Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
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
up vote 0 down vote accepted

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.

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.