# Using group theory to prove results in number theory

• Apr 16th 2012, 03:41 AM
Sylvia104
Using group theory to prove results in number theory
I was interested in the subject of quadratic residues recently. Let $p$ be an odd prime. We say that an integer $a$ is a quadratic residue $\mod p$ iff there exists an integer $x$ such that $a\equiv x^2\mod p,$ otherwise we say that $a$ is a quadratic non-residue $\mod p.$

Let $R_p$ be the set of all quadratic residues $\mod p.$ Then, you know what? $R_p$ is a subgroup of index $2$ of $\mathbb Z_p^\times,$ the multiplicative group of the field $\mathbb Z_p$ of integers $\mod p!$ This is not mentioned in a number of books and websites on quadratic residues I've seen, but I think a development based on this group-theoretic approach can advance our understanding of results in number theory, in particular quadratic residues.

Watch the following space. (Wink)
• Apr 16th 2012, 04:11 AM
Sylvia104
Re: Using group theory to prove results in number theory
Let $p$ be an odd prime and $R_p$ the set of all quadratic residues $\mod p.$

Lemma 1: $\left|R_p\right|=\frac{p-1}2$

Proof:
We have $R_p=\{x^2\mod p:1\leqslant x\leqslant p-1\}.$ But note that $x^2\equiv(p-x)^2\mod p.$ Hence we can write $R_p=\{x^2\mod p:1\leqslant x\leqslant\tfrac{p-1}2\}$ since $1\leqslant x\leqslant\tfrac{p-1}2\Leftrightarrow\tfrac{p-1}2+1\leqslant p-x\leqslant p-1.$ This shows that there are at most $\frac{p-1}2$ distinct quadratic residues $\mod p.$ But now suppose that $1\leqslant x_1,x_2\leqslant p-1$ and $x_1^2\equiv x_2^2\mod p.$ Then $p\mid\left(x_1^2-x_2^2\right)=(x_1-x_2)(x_1+x_2)$ $\implies$ $p\mid(x_1-x_2)$ or $p\mid(x_1+x_2).$ The latter would imply that $x_1\equiv p-x_2\mod p$ which is impossible for $0 Hence $x_1\equiv x_2\mod p$ $\implies$ $x_1=x_2$ if $0 This proves that there are exactly $\frac{p-1}2$ quadratic residues $\mod p.$
• Apr 16th 2012, 04:25 AM
Sylvia104
Re: Using group theory to prove results in number theory
Lemma 2:
(i) $R_p$ is closed under multiplication $\mod p.$
(ii) The multiplicative inverse of $a\in R_p$ is in $R_p.$

Proof:
(i) If $a\in R_p$ and $b\in R_p$ then $a\equiv x^2\mod p$ and $b\equiv y^2\mod p$ for some integers $x,y.$ Thus $ab\equiv x^2y^2\mod p=(xy)^2\mod p$ and so $ab\in R_p.$

(ii) Let $b$ be a multiplicative inverse of $a\in R_p.$ Then $b=1\cdot b=(ab)b=ab^2$ is a product of two quadratic residues $a$ and $b^2$ and we have just proved that such a product is a quadratic residue.
• Apr 16th 2012, 04:44 AM
Sylvia104
Re: Using group theory to prove results in number theory
Lemmas 1 & 2 imply that $R_p$ is a subgroup of index $2$ of $\mathbb Z_p^\times,$ the multiplicative group of the field of integers $\mod p.$ It is well known that the group $\mathbb Z_p^\times$ is cyclic, i.e. $\mathbb Z_p^\times=\left$ where $k$ is a primitive root $\mod p.$ Clearly $k\notin R_p$ otherwise $k$ would not generate anything bigger than $R_p.$ Thus primitive roots are not quadratic residues.

Using this, we can prove a number of results in quadratic-residue theory using elementary results in group theory. The following result is especially useful.

Lemma 3:
Let $G$ be a group and $H$ a subgroup of index $2.$ Then
$\forall a,b\in G,ab\in H\Leftrightarrow a,b\in H\text{ or }a,b\notin H.$
Equivalently,
$\forall a,b\in G,ab\notin H\Leftrightarrow$ one of $a$ and $b$ is in $H$ and the other is not.

The proof of Lemma 3 is extremely easy; I leave it as an exercise for the reader. (Tongueout)
• Apr 16th 2012, 05:14 AM
Sylvia104
Re: Using group theory to prove results in number theory
We start by proving a elementary result in quadratic-residue theory. First, an explanation about notation (for those who are not familiar with number theory). If $p$ is an odd prime and $a$ is an integer coprime with $p,$ then we write

$\left\(\frac ap\right)=\left\{\begin{array}{rc}1 & a\in R_p\\ -1 & a\notin R_p\end{array}\right.$

The notation $\left(\frac**\right)$ is called the Legendre symbol.

T1: Let $p$ be an odd prime and $a,b$ integers coprime with $p.$ Then $\left(\frac{ab}p\right)=\left(\frac ap\right)\left(\frac bp\right).$

Proof:
We take integers $a,b$ coprime with $p$ and reduce them $\mod p.$ Then we just check three cases: (i) $a,b\in R_p,$ (ii) $a,b\notin R_p,$ (iii) one of $a$ and $b$ is in $R_p$ and the other is not. Now this smacks something of Lemma 3, doesn't it? Indeed it does – and I leave the completion of the proof to the interested reader. (Tongueout)

But I hope you see my point. Lemma 3 is a result in group theory (nothing to do with quadratic residues) but it can be used to prove a result about quadratic residues via the fact that thet the set $R_p$ is a subgroup of a larger group. Do you see? (Cool)

Incidently, this shows that the mapping $f:\left(\mathbb Z_p^\times\right)\to\{1,-1\}$ with $f(a)=\left(\frac ap\right)$ is a homomorphism with kernel $R_p.$
• Apr 16th 2012, 05:50 AM
Sylvia104
Re: Using group theory to prove results in number theory
We prove the next result, which is Euler's criterion:

T2: If $p$ is an odd prime and $a$ is an integer coprime with $p,$ then $\left(\frac ap\right)\equiv a^{\frac{p-1}2}\mod p.$

There are two things to note before we proceed with the proof. First, $a^{\frac{p-1}2}$ can only be $\equiv\pm1\mod p.$ This is because $a^{p-1}\equiv1\mod p$ by Fermat and $a^{p-1}-1=\left(a^{\frac{p-1}2}-1\right)\left(a^{\frac{p-1}2}+1\right).$ Second, if $a$ is a quadratic non-residue $\mod p,$ then $a$ can be expressed as $a=kr,$ where $k$ is primitive root $\mod p$ and $r\in R_p.$ This again comes from the coset property of $R_p;$ more about this later. (Wink)
• May 12th 2012, 01:34 AM
Deveno
Re: Using group theory to prove results in number theory
Quote:

Originally Posted by Sylvia104
We prove the next result, which is Euler's criterion:

T2: If $p$ is an odd prime and $a$ is an integer coprime with $p,$ then $\left(\frac ap\right)\equiv a^{\frac{p-1}2}\mod p.$

There are two things to note before we proceed with the proof. First, $a^{\frac{p-1}2}$ can only be $\equiv\pm1\mod p.$ This is because $a^{p-1}\equiv1\mod p$ by Fermat

and Fermat by Lagrange. indeed Fermat's "little theorem" generalizes quite naturally to one of Euler: $a^{\varphi(n)} \equiv 1 \mod n$, if $(a,n) = 1$

Quote:

and $a^{p-1}-1=\left(a^{\frac{p-1}2}-1\right)\left(a^{\frac{p-1}2}+1\right).$ Second, if $a$ is a quadratic non-residue $\mod p,$ then $a$ can be expressed as $a=kr,$ where $k$ is primitive root $\mod p$ and $r\in R_p.$ This again comes from the coset property of $R_p;$ more about this later. (Wink)
i am looking forward to your proof that the "other coset" of $R_p$ must necessarily contain a primitive root (i suspect you'll need to show we are dealing with cyclic groups).