# Prove that if $ab \equiv 1 \pmod{p}$ and $a$ is quadratic residue mod $p$, then so is $b$

Prove that if $ab \equiv 1 \pmod{p}$ and $a$ is quadratic residue mod $p$, then so is $b$ where $p$ is odd prime, and $(a,p) = (b,p) = 1$.

Besides $b$ is the inverse of $a$, what else does this $ab \equiv 1 \pmod{p}$ tell us? A hint would be greatly appreciated.

Thank you,

-

The definitions I am using are:

• $a$ is a square iff $a = x^2 \pmod p$ for some $x$.
• $a^{-1}$ is the unique (prove that it's unique if you haven't already!) number satisfying $a a^{-1} \equiv 1 \pmod p$.

Rewrite the equation as $b \equiv a^{-1} \pmod p$.

Then you notice that $a$ being a square: $a \equiv x^2 \pmod p$.

Implies that $b$ is a square: $b \equiv a^{-1} \equiv (x^2)^{-1} \equiv (x^{-1})^2 \equiv y^2 \pmod p$. (where $y \equiv x^{-1} \pmod p$).

-
@quanta: usually, $\displaystyle a^{b^c}$ means $a^{(b^c)}$, not $(a^b)^c$. So $x^{-1^2}$ means, at best $x^{(-1)^2} = x^1 = x$; in fact, since the exponent takes precedence over the sign, it would normally be interpreted as $\displaystyle x^{-(1^2)} =x^{-1}$. You mean $(x^{-1})^2$. –  Arturo Magidin Apr 13 '11 at 19:21
@Arturo, Good point, thanks! –  quanta Apr 13 '11 at 19:25
@Chan: No: $(x^{-1})^2 = x^{-2}$. The laws of exponentiation have not been repealed yet. –  Arturo Magidin Apr 13 '11 at 19:49
@Chan: Huh? You know that $x^{-2}$ is a square, because it is equal to $(x^{-1})^2$. But since the laws of exponentiation have not been repealed, then$$(a^b)^c = a^{bc} = a^{cb} = (a^c)^b.$$Since $x^2\equiv a\pmod{p}$, then$$(x^{-1})^2 = x^{-2} = (x^2)^{-1} \equiv a^{-1} \equiv b\pmod{p}.$$This is essentially basic algebra, not even congruence arithmetic. –  Arturo Magidin Apr 13 '11 at 20:01
@Chan: In order to say that $b$ is a quadratic residue, there has to exist some integer $w$ such that $w^2\equiv b\pmod{p}$. What you call $w$ is completely irrelevant. You can call it $w$; you can call it $z$; you can call it $x$; you can call it "Steve". "Steve" is then a "witness to the fact that $b$ is a quadratic residue." Steve shows that $b$ is a square modulo $p$. If $x$ is the name of the witness to the fact that $a$ is a quadratic residue, then it turns out that $x^{-1}$, the modular inverse of $x$, is a witness for $b$. You are missing the point because of the notation. –  Arturo Magidin Apr 13 '11 at 20:18

The fact that $b$ is the modular inverse of $a$ is more than enough.

If these were the rationals, if $r^2 = a$ (with $r$ and $a$ rationals), then is $\frac{1}{a}$ a square? What number works as the square of $\frac{1}{a}$?

Now do the same thing, but modulo $p$.

-
Thank you. –  Chan Apr 13 '11 at 19:34

If $ab\equiv 1$ and $x^2 \equiv a$ then $(xb)^2 = x^2 b^2 \equiv a b^2 \equiv b$, and so $b$ is a quadratic residue.

-

Suppose that $a$ is a quadratic residue modulo $p$. Then for some $x$, $x^2\equiv a \pmod{p}$. Let $y$ be the inverse of $x$. Then $x^2y^2=(xy)^2\equiv 1 \pmod{p}$.

Thus $a(y^2) \equiv 1 \pmod{p}$, meaning that $y^2\equiv b \pmod{p}$, since the inverse of any element is uniquely defined modulo $p$. So we have found a number $y$ such that $y^2 \equiv b \pmod{p}$, and therefore $b$ is a quadratic residue.

-
@user6312: Thank you. –  Chan Apr 13 '11 at 19:35
HINT $\$ hom's $\rm\:h\:$ preserve squares: $\rm\ a = c^2\ \Rightarrow\ h(a) = h(c^2) = (h(c))^2\:.\:$ Yours is the special case $\rm\:h(x) = x^{-1}\:,\:$ i.e. $\rm\ a = c^2\ \Rightarrow\ a^{-1} = (c^{-1})^2\:.$
Thanks. As you mentioned even if $ab \equiv k \pmod{p}$, we can still can prove it? –  Chan Apr 14 '11 at 5:51