Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

Conjecture :

Let $p$ be a prime number such that : $p \equiv 1 \pmod 4$

If multiplicative order of : $b \pmod p$ is $p-1$ then

multiplicative order of : $(p-b) \pmod p$ is $p-1$ .

In other words :

$b^k \equiv 1 \pmod p$ and $(p-b)^k \equiv 1 \pmod p$

for $k=p-1$ , and no $k$ less than this .

Maple code that examines this conjecture :

p := 37;

for b from 2 to p-1 do

i := 0;

for k from 1 to p-1 do

if b^k mod p = 1 then

i := i+1;

end if;

end do;

if i = 1 then

print(b) ;

end if;

end do;

What proof strategy one should use in order to prove this conjecture ?

share|cite|improve this question
up vote 3 down vote accepted

The conjecture is true. Assume that the order of $b\pmod p$ equals $p-1$. Let $k$ be an integer such that $(p-b)^k\equiv 1\pmod p$; we want to prove that $k$ is a multiple of $p-1$.

Note that $p-b \equiv (-1)b \pmod p$, and so $(-1)^k b^k \equiv 1\pmod p$. There are two cases:

(1) $k$ is even and $b^k \equiv 1\pmod p$. Then we already know that $k$ is a multiple of $p-1$.

(2) $k$ is odd and $b^k\equiv -1\pmod p$. But this is impossible: if $b^k\equiv -1\pmod p$ then $b^{2k}\equiv 1\pmod p$, which means that $2k$ is a multiple of $p-1$, which means that $k$ is a multiple of the even number $(p-1)/2$ - here we use the fact that $p\equiv1\pmod4$.

share|cite|improve this answer

If $b$ is one such element, then it is a primitive root of that prime. Thus $b^k$ is -1 where k=(p-1)/2. Then$-b$ is $b^{k+1}$. If k is odd, then the g.c.d. of k+1 and p-1 is 2, whereas in the other case the greatest common divisor should be 1, thus the result.
Now suppose that the order of $a$ is $n$, so that $a \equiv b^{(p-1)/n} \pmod p$, and that $ab \equiv b^{(p+n-1)/n} \pmod p$. Denote $(p+n-1)/n$ by α. Then the order of $ab$ should be $(p-1)/g.c.d.(p-1,α)$. This I shall suppose to be the most general non-trivial result.
P.S. Here two congruent numbers are for the sake of convenience referred to as the same.

share|cite|improve this answer
I saw the answer of Greg after I posted, for pondering over and over again upon the way to formulate it. Sorry for some duplicate part in common. Hope this does not make this answer a nuisance. – awllower Jan 30 '12 at 14:35

$$(b^{(p-1)} \equiv 1 \pmod{p}) \land (2\ |\ (p-1))\\ \Rightarrow \\ (-1)^{(p-1)}(b)^{(p-1)} \equiv 1 \pmod{p}\\ \Rightarrow \\ (-b)^{(p-1)} \equiv 1 \pmod{p} \\ \Rightarrow \\ (p-b)^{(p-1)} \equiv 1 \pmod{p} $$

Which proves that the order of $p-b$ divides $p-1$.

Let's say that $k$ is the smallest integer such that $b^k\equiv1\mod{p}$

$$ k<(p-1) \ \land \ (p-b)^k \equiv 1 \pmod{p}\\ \Rightarrow \\ (-1)^k b^k \equiv 1 \pmod{p} \\ $$

We have two possibilites:

(1) $2 | k \Rightarrow b^k \equiv 1 \pmod{p} \Rightarrow (p-1)|k \Rightarrow k=p-1$

(2) $2 \nmid k \Rightarrow b^k \equiv -1 \pmod{p} \Rightarrow b^{2k} \equiv 1 \pmod{p} \Rightarrow (p-1)|2k$; $\exists \ k'\quad p = 1+4k' \\ \Rightarrow 4k' | 2k \Rightarrow 2|k\\$

Which means that the only possibility is $k = p-1$. $\Box$

Sorry for the answer similar to one already given; I had started before, but it took ages to learn how to write formulas in TeX, and I don't want to just throw the answer away XD

share|cite|improve this answer

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.