1
$\begingroup$

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.

  • 4
    What did you try?2012-10-28
  • 1
    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.2012-10-28
  • 0
    I have rephrased the problem, thank you for your suggestion. @AndréNicolas2012-10-29
  • 1
    What does ${\cal O}_p$ mean?2012-10-29
  • 0
    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$.2012-10-29
  • 0
    OK, but the question is still not clear. Are you saying, "for all $a,b$ etc. etc.", or are you saying "there exist $a,b$ such that etc., etc."?2012-10-29
  • 0
    Well if the $b$ is to fulfill the condition $p \nmid b$ then clearly it's not FOR ALL but some $b$; similarly for a.2012-10-29
  • 0
    Nothing is clear until the person asking the question writes it clearly.2012-10-29

1 Answers 1

0

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.

  • 0
    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.2012-10-29
  • 0
    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.2012-10-29
  • 0
    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$).2012-10-29
  • 0
    That's the point, that's where the contradiction is derived to show $p$ must be of that form!2012-10-30
  • 0
    @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$?2012-10-31
  • 0
    Now that the question has been edited so I can understand it, I finally understand the answer. I think what's confusing me is you write of the number of values of $b$ that satisfy the conditions, when I think you mean the number of values of $x$ that satisfy the conditions. With that change, I think you have answered the question, and I hope OP will agree or will ask for clarification.2012-10-31
  • 0
    Well its pretty easy to prove if $p = 2^n + 1$ is prime then $n$ is a power of 2. Its also quite well-known, google Fermat prime to get dozens of proofs.2012-10-31
  • 0
    fmat, it is easy to show that if $2^n+1$ is prime then $n$ is a power of 2. Think about factoring $a^m+b^m$ when $m$ has an odd factor.2012-10-31
  • 0
    Thank you two very much; I will review the proof that disobey gave once again and hopefully mark this problem solved soon.2012-10-31
  • 0
    Sorry but I cannot see why by picking $p-1 - \phi(p-1)$ values of $b$ that satisfy the conditions we have at least $p-1 - \phi(p-1)$ distinct elements of order $p-1$?2012-10-31