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 $\displaystyle p$ be an odd prime. We say that an integer $\displaystyle a$ is a quadratic residue $\displaystyle \mod p$ iff there exists an integer $\displaystyle x$ such that $\displaystyle a\equiv x^2\mod p,$ otherwise we say that $\displaystyle a$ is a quadratic non-residue $\displaystyle \mod p.$

Let $\displaystyle R_p$ be the set of all quadratic residues $\displaystyle \mod p.$ Then, you know what? $\displaystyle R_p$ is a subgroup of index $\displaystyle 2$ of $\displaystyle \mathbb Z_p^\times,$ the multiplicative group of the field $\displaystyle \mathbb Z_p$ of integers $\displaystyle \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 $\displaystyle p$ be an odd prime and $\displaystyle R_p$ the set of all quadratic residues $\displaystyle \mod p.$

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

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

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

(ii) Let$\displaystyle b$ be a multiplicative inverse of $\displaystyle a\in R_p.$ Then $\displaystyle b=1\cdot b=(ab)b=ab^2$ is a product of two quadratic residues $\displaystyle a$ and $\displaystyle 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 $\displaystyle R_p$ is a subgroup of index $\displaystyle 2$ of $\displaystyle \mathbb Z_p^\times,$ the multiplicative group of the field of integers $\displaystyle \mod p.$ It is well known that the group $\displaystyle \mathbb Z_p^\times$ is cyclic, i.e. $\displaystyle \mathbb Z_p^\times=\left<k\right>$ where $\displaystyle k$ is a primitive root $\displaystyle \mod p.$ Clearly $\displaystyle k\notin R_p$ otherwise $\displaystyle k$ would not generate anything bigger than $\displaystyle 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 $\displaystyle G$ be a group and $\displaystyle H$ a subgroup of index $\displaystyle 2.$ Then
$\displaystyle \forall a,b\in G,ab\in H\Leftrightarrow a,b\in H\text{ or }a,b\notin H.$
Equivalently,
$\displaystyle \forall a,b\in G,ab\notin H\Leftrightarrow$ one of $\displaystyle a$ and $\displaystyle b$ is in $\displaystyle 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 $\displaystyle p$ is an odd prime and $\displaystyle a$ is an integer coprime with $\displaystyle p,$ then we write

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

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

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

Proof:
We take integers $\displaystyle a,b$ coprime with $\displaystyle p$ and reduce them $\displaystyle \mod p.$ Then we just check three cases: (i) $\displaystyle a,b\in R_p,$ (ii) $\displaystyle a,b\notin R_p,$ (iii) one of $\displaystyle a$ and $\displaystyle b$ is in $\displaystyle 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 $\displaystyle R_p$ is a subgroup of a larger group. Do you see? (Cool)

Incidently, this shows that the mapping $\displaystyle f:\left(\mathbb Z_p^\times\right)\to\{1,-1\}$ with $\displaystyle f(a)=\left(\frac ap\right)$ is a homomorphism with kernel $\displaystyle 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 $\displaystyle p$ is an odd prime and $\displaystyle a$ is an integer coprime with $\displaystyle p,$ then $\displaystyle \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, $\displaystyle a^{\frac{p-1}2}$ can only be $\displaystyle \equiv\pm1\mod p.$ This is because $\displaystyle a^{p-1}\equiv1\mod p$ by Fermat and $\displaystyle a^{p-1}-1=\left(a^{\frac{p-1}2}-1\right)\left(a^{\frac{p-1}2}+1\right).$ Second, if $\displaystyle a$ is a quadratic non-residue $\displaystyle \mod p,$ then $\displaystyle a$ can be expressed as $\displaystyle a=kr,$ where $\displaystyle k$ is primitive root $\displaystyle \mod p$ and $\displaystyle r\in R_p.$ This again comes from the coset property of $\displaystyle 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 $\displaystyle p$ is an odd prime and $\displaystyle a$ is an integer coprime with $\displaystyle p,$ then $\displaystyle \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, $\displaystyle a^{\frac{p-1}2}$ can only be $\displaystyle \equiv\pm1\mod p.$ This is because $\displaystyle a^{p-1}\equiv1\mod p$ by Fermat

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

Quote:

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