2
$\begingroup$

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,

5 Answers 5

1

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\:.$

  • 0
    Thanks. As you mentioned even if $ab \equiv k \pmod{p}$, we can still can prove it?2011-04-14
3

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$.

3

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.

2

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$).

  • 0
    @Chan, I have added$a$bit more detail and clarification.2011-04-13
1

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.

  • 0
    @user6312: Thank you.2011-04-13