 Nontrivial square root of unity modulo an integer

For an odd integer $N>1$, a nontrivial square root of unity modulo $N$ is a residue $z$ with $z^2\equiv 1(\mathrm{mod}N)$ and $z\not\equiv \pm 1(\mathrm{mod}N)$. Then both $\gcd (z-1,N)$ and $\gcd (z+1,N)$ are proper divisors. For $N=77$, $z=34$ works: $34^2\equiv 1(\mathrm{mod}77)$, $\gcd (33,77)=11$, and $\gcd (35,77)=7$.

A congruence of squares with $\gcd (b,N)=1$ converts to this form by $z\equiv a{b}^{-1}(\mathrm{mod}N)$, using a modular multiplicative inverse. In the $a=20,b=13$ example, $13^{-1}\equiv 6(\mathrm{mod}77)$, so $z\equiv 20\cdot 6\equiv 43(\mathrm{mod}77)$. It yields $\gcd (42,77)=7$ and $\gcd (44,77)=11$. Nontriviality requires mixed sign choices across prime factors, which an odd prime number modulus cannot provide.