Q:

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 ?

A:

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

