Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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,

share|improve this question
add comment

5 Answers

up vote 1 down vote accepted

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

share|improve this answer
    
@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
3  
@Chan: No: $(x^{-1})^2 = x^{-2}$. The laws of exponentiation have not been repealed yet. –  Arturo Magidin Apr 13 '11 at 19:49
1  
@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
2  
@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
show 5 more comments

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

share|improve this answer
    
Thank you. –  Chan Apr 13 '11 at 19:34
add comment

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.

share|improve this answer
add comment

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.

share|improve this answer
    
@user6312: Thank you. –  Chan Apr 13 '11 at 19:35
add comment

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

share|improve this answer
    
Thanks. As you mentioned even if $ab \equiv k \pmod{p}$, we can still can prove it? –  Chan Apr 14 '11 at 5:51
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.