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.

For the special case $ab \equiv 1 \pmod{p}$, I already got very clear explanation from Arturo Magidin and Quanta in this thread Prove that if $ab \equiv 1 \pmod{p}$ and $a$ is quadratic residue mod $p$, then so is $b$

Now if $ab \equiv r \pmod{p}$, what condition need to be hold in order for this to be true, i.e If $a$ is quadratic residue modulo $p$, then $b$ is also quadratic residue modulo $p$. My attempt was, I made a concrete example to observe the value of $r$, says $p = 7$. The results are: 1, 4, 5 $$1^2 \equiv 1 \pmod{7}$$ $$2^2 \equiv 4 \pmod{7}$$ $$3^2 \equiv 2 \pmod{7}$$ $$4^2 \equiv 1 \pmod{7}$$ $$5^2 \equiv 4 \pmod{7}$$ $$6^2 \equiv 1 \pmod{7}$$

So $r$ could be $1$, $2$, $4$, since $4.4 \equiv 1 \pmod{7}$ and $4.2 \equiv 1 \pmod{7}$. From these results, I saw that $r$ was also quadratic residue modulo $p$. Another idea that I tried is adapting the proof from the mentioning thread above: If $ab \equiv r \pmod{p}$, then $$aa^{-1}b \equiv ra^{-1} \pmod{p} \Leftrightarrow b \equiv ra^{-1} \pmod{p}$$ $$bb^{-1}a \equiv rb^{-1} \pmod{p} \Leftrightarrow a \equiv rb^{-1} \pmod{p}$$

Then I tried to use the fact that $x^2 \equiv a \pmod{p}$, and $a \equiv rb^{-1} \pmod{p}$ to come with $x^2 \equiv rb^{-1} \pmod{p}$. But I could not find a way to express this in term of $y^2 \equiv b \pmod{p}$. Furthermore, I don't know if this algebraic manipulation could solve the condition for $r$ or not. Any idea? A hint would be greatly appreciated.

Thank you

share|improve this question
1  
You are on the right track. It turns out that $b$ is a quadratic residue of $p$ if and only if $r$ is. The easy direction is if $a$ is QR and $b$ is $QR$, then $r$ is QR. This is just the fact that $x^2y^2=(xy)^2$. For the other direction, suppose $r$ is QR and $a$ is QR. By the result of the previous post, $a^{-1}$ is QR. But $b=ra^{-1]$, so $b$ is the product of two QR, hence QR. –  André Nicolas Apr 14 '11 at 7:32
    
@user6312: Thank you. I will try it again. –  Chan Apr 14 '11 at 7:34
add comment

3 Answers 3

up vote 6 down vote accepted

The following three facts are relevant.

  • If $a$ and $b$ are squares then $r$ is a square.

  • If $a$ and $b$ are not squares then $r$ is a square.

  • If one of $a,b$ is a square and the other is not then $r$ is not a square.

It's simple to prove the first one: Let $a = x^2$, $b = y^2$ so that $r = ab = (xy)^2$.

As for the next two I will give a "hi-tech" proof (See Martins comment for a direct proof).

Modular arithmetic $\mathbb{Z}/p\mathbb{Z}$ is a ring, but the group of units $(\mathbb{Z}/p\mathbb{Z})^\times$ is a group: It's the multiplicative part of the ring. The only non-unit is $0$ so as a set it's $\{1,2,\cdots,p-1\}$.

This group is cyclic (a very fundamental and strong theorem, see here for some discussion on it) and we can use this to prove the theorems: Let $g$ generate the group, so that every element is of the form $g^k$ for some $0 < k < p-1$,

  • First note that $a$ is a square iff $a = g^{2k}$. (Easy to prove).

Let $a = g^u$, $b = g^v$ so $r = ab = g^{u+v}$. All three facts are an easy deduction from this. You can prove them now but I would like to define some good notation.

We can introduce the Legendre symbol now: Define a map $\left(\tfrac{-}{p}\right)$ that takes $g$ to $-1$ and extend it to the whole group: It's a group homomorphism from the units group $\mathbb{Z}/p\mathbb{Z}$ into $\{1,-1\}$. It's $1$ exactly when the number is a square and $0$ otherwise.

So now we have:

  • If $a$ and $b$ are squares then $r$ is a square because $\left(\tfrac{r}{p}\right) = \left(\tfrac{ab}{p}\right) = \left(\tfrac{a}{p}\right)\left(\tfrac{b}{p}\right) = 1 \cdot 1 = 1$.

  • If $a$ and $b$ are not squares then $r$ is a square because $\left(\tfrac{r}{p}\right) = \left(\tfrac{ab}{p}\right) = \left(\tfrac{a}{p}\right)\left(\tfrac{b}{p}\right) = -1 \cdot -1 = 1$.

  • If one of $a,b$ is a square and the other is not then $r$ is not a square because $\left(\tfrac{r}{p}\right) = \left(\tfrac{ab}{p}\right) = \left(\tfrac{a}{p}\right)\left(\tfrac{b}{p}\right) = 1 \cdot -1 = -1$.

share|improve this answer
2  
A different approach to prove your three facts would be showing: 1. There are exactly (p-1)/2 squares and (p-1)/2 non-squares. 2. For a fixed a, the values ab run through the whole Zp. 3. Showing the first fact directly, the second fact by contradiction (using the inverse). 4. The fourth fact follows now by counting argument. (We have already used all (p-1)/2 non-squares, the remaining values must be squares.) Nevertheless, I do agree that it is good to be familiar with Legendre symbol, this was just a side note. –  Martin Sleziak Apr 14 '11 at 11:21
1  
@Martin, Thank you for the clever proof! I had never thought of this! I tried to come up with direct arguments like that but couldn't. –  quanta Apr 14 '11 at 11:45
    
Thanks for your "hi-tech" proof ;)! By the way, is there a way to prove it without using group-theory? since I've not learnt it yet. –  Chan Apr 14 '11 at 23:47
    
@Chan, Is there something you didn't understand? I think any of this is "group theory" I just call a group a group. –  quanta Apr 15 '11 at 9:44
    
I think I got it now, thank you ;) –  Chan Apr 15 '11 at 17:22
add comment

What you are observing is simply the addition tables for $\rm\ \mathbb Z/2\ \cong G/G^2,\:\ G = \mathbb (Z/p)^{*}\:.\:$ Because the squares form a subgroup of index $2$, they multiply the same as addition mod $2\ $ (parity addition). More precisely, with the notation: Square $\rm = S \to 0\in \mathbb Z/2\:,\ $ Nonsquare $\rm = N\to 1\in \mathbb Z/2\:,\: $ we have

$$\rm S \:*\: S\:\ =\ \:S\:\ \ \iff\ \ \ 0 + 0\ \equiv\ 0 $$

$$\rm S \:* N\ =\ N\ \ \iff\ \ \ 0 + 1\ \equiv\ 1 $$

$$\rm N * N\ =\ S\ \ \iff\ \ \ 1 + 1\ \equiv\ 0 $$

You can find further examples in my post a couple days ago, which describes various ways of characterizing subgroups, including the complementary view of a subgroup. When you are first learning elementary number theory and group theory, in order to better comprehend the abstract algebraic structures, it is essential to explore many concrete instances of these abstractions. As you can see from the many examples in my linked post, such subgroup laws (and their complements) are already well-known subconsciously in the familiar number systems. The algebraic abstractions serve to "reify" this intuitive knowledge in a more formal structured manner. This is essential in order to cope with such structure when it arises in much more complex scenarios.

share|improve this answer
    
Many thanks for your answer. However, I haven't learnt group-theory and abstract algebra yet. I guess your answer must be very elegant and concise, but for now, I really don't have enough knowledge to go through it since this is my first Mathematics course beyond Calculus A, B, C. Anyhow, I will come back to it later when I'm ready. I wonder is there a proof without using group-theory and abstract algebra? –  Chan Apr 14 '11 at 23:46
    
@Chan I presumed from your prior questions on reciprocity, Jacobi's symbol, Hensel's lemma, etc. that you knew some basic algebra. If you are attempting to learn these topics without such then I strongly recommend against doing so. To truly grasp the innate structures behind these results requires basic knowledge of algebra. Without such you may as well try to paint a portrait with your hands tied behind your back. –  Bill Dubuque Apr 15 '11 at 0:04
add comment

We are working in the multiplicative group $G=(\mathbb{Z}/p\mathbb{Z})^*$. This group is cyclic with order $p-1$, which is even for $p \neq 2$. Then $G^2$, consisting of the squares of elements in $G$, is an index 2 subgroup. The set of nonsquares is just the coset of $G^2$ in $G$.

We can immediately conclude:

  1. The product of two squares is a square.
  2. The product of a square and a nonsquare is a nonsquare.
  3. The product of two nonsquares is a square.
share|improve this answer
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.