Using group theory to prove results in number theory

**Sylvia104** · April 16th 2012, 03:41 AM

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.

**Sylvia104** · April 16th 2012, 04:11 AM

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<x_1,x_2<p.$ Hence $x_1\equiv x_2\mod p$ $\implies$ $x_1=x_2$ if $0<x_1,x_2<p.$ This proves that there are exactly $\frac{p-1}2$ quadratic residues $\mod p.$

**Sylvia104** · April 16th 2012, 04:25 AM

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.

**Sylvia104** · April 16th 2012, 04:44 AM

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<k\right>$ 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.

**Sylvia104** · April 16th 2012, 05:14 AM

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.

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?

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

**Sylvia104** · April 16th 2012, 05:50 AM

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.

**Deveno** · May 12th 2012, 01:34 AM

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$

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.

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

Thread: Using group theory to prove results in number theory

LinkBack

Thread Tools

Display

Using group theory to prove results in number theory

Re: Using group theory to prove results in number theory

Re: Using group theory to prove results in number theory

Re: Using group theory to prove results in number theory

Re: Using group theory to prove results in number theory

Re: Using group theory to prove results in number theory

Re: Using group theory to prove results in number theory

Similar Math Help Forum Discussions

Textbooks on Galois Theory and Algebraic Number Theory

Group Theory - Prove that for ab-cd=1, there is no cancellation for (a+c)/(b+d)

Group Theory-Show no infinite soluble group has a composition series

Quick questions on Group Theory - Cosets / Normal Group

Group Theory - Sylow Theory and simple groups

Search Tags