Suppose $n \in \mathbb{N}$ is odd and $$ 2^{\frac{n-1}{2}} \equiv k \mod n,$$ where $k \neq \pm1$. Show that $n$ is composite.
My work:
I got this far and get stuck:
Basically I took the square root of both sides and now have
$$ 2^{n-1} \equiv k^{2} \mod n .$$ If $k$ is prime, then LHS would be 1 by Fermat's little theorem, so $k^{2} \equiv 1 \mod n$
SO now I'm stuck; is it something to do with the fact that $k^{2}$ cant be $1$, because $k$ only would have one multiplicative inverse ($\mod n$) if $n$ were prime?
$n$ odd prime $\Rightarrow 2^{n-1} \equiv 1 \mod n \Rightarrow k^2 \equiv 1 \mod n \Rightarrow k \equiv \pm1 \mod n.$