Show mn has order $2^c$ mod p Let p be an odd prime such that p doesn't divide mn and each $m,n$ has order $2^d$ modulo p, where $2^d|p-1$. Prove that $mn$ has order $2^c$ modulo p, where $0 \le c\le d-1$.
So $(2^d,p) = 1$ and $m^{2^d}=1$ mod(p) and $n^{2^d}=1$(mod p)...

Note that $x = m^{2^{d-1}}$ satisfies $x^2 = m^{2^d} = 1$, implying that $x = -1$ mod $p$ since $x \ne 1$ because $2^{d-1}$ is strictly less than the multiplicative order of $m$ modulo $p$, and $\pm 1$ are the only elements squaring to $1$ mod $p$.  Similarly, $n^{2^{d-1}} = -1$ mod $p$.
This gives us $(mn)^{2^{d-1}} = m^{2^{d-1}}n^{2^{d-1}} = (-1)(-1) = 1$ mod $p$.  Therefore, the order of $mn$ is a divisor of $2^{d-1}$, as desired.
