# Multiplicative Order of $b \pmod p$ , where $p \equiv 1 \pmod 4$

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 ?

-

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$.

-

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.

-
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

-