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$.
A: 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.
A: $$
(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 $(p-b) ^k\equiv1\mod{p}$
$$
(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 write it
