Suppose $x$ is a perfect square mod $n$. If $xy \equiv 1 $ mod $n$, prove $y$ is a perfect square also.

Question

Here's what I have:

If $a$ is a perfect square mod $n$, then $\exists m \in \mathbb{Z}^+$ such that $m^2 \equiv a \text{ mod } n$. We want to find some $k$ such that $k^2 \equiv b \text{ mod } n$. \begin{align*} ab &\equiv 1 \text{ mod } n \\ m^2b &\equiv 1 \text{ mod } n \\ b &\equiv m^{-2} \text{ mod } n \end{align*}

Is this satisfactory? Thanks!

Answer 1

We have $a \equiv m^2 \mod n$. And we have $ab \equiv 1 \mod n$.

So $(mb)^2 \equiv m^2b^2 \equiv ab^2 \equiv (ab)b \equiv b \mod n$.

Answer 2

This is not an improvement on fleablood's Answer but might give you some insights.... All values here are integers.

Theorem. For all non-zero $x,y$: There exist $u,v$ such that $ux+vy=1$ iff $\gcd(x,y)=1.$ Equivalently, there exists $u$ such that $ux\equiv 1\pmod y$ iff $\gcd(x,y)=1.$

Corollary: The Fundamental Theorem of Arithmetic (FTA) : For all non-zero $x,y,z,$ if $y|\;xz$ and $\gcd(y,x)=1$ then $y|z.$ Because, with $ux+vy=1$ we have $y|\;u(xz)=(ux)z=(1-vy)z=z-y(vz)\implies y|z.$

By the Theorem, $ab\equiv 1\pmod n\implies \gcd(a,n)=1.$Now since $a-m^2\equiv 0\pmod n$ for some $m,$ we have $\gcd(m,n)=1.$

.... Because if $p|\;m$ and $p|\;n$ then $p|\;m^2 ,$ hence $p|\; (a-m^2) \land p|\;m^2,$ so $p|(a-m^2)+m^2=a$... But $(p|a\land p|\;n)\implies p=\pm 1 .$

Since $\gcd(m,n)=1,$ the Theorem implies there exists $u$ with $um\equiv 1 \pmod n.$ Now $1\equiv u^2m^2\equiv u^2a\equiv ba \pmod n.$ So $n|\;(u^2-b)a.$

Since $\gcd(a,n)=1,$ the FTA implies $n|(u^2-b).$