6
$\begingroup$

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

  • 0
    @user6312: Thank you. I will try it again.2011-04-14

3 Answers 3

6

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

  • 0
    I think I got it now, thank you ;)2011-04-15
5

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.

  • 0
    @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.2011-04-15
3

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.