Results 1 to 7 of 7

Thread: Using group theory to prove results in number theory

  1. #1
    Member Sylvia104's Avatar
    Joined
    Mar 2012
    From
    London, UK
    Posts
    107
    Thanks
    37

    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.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member Sylvia104's Avatar
    Joined
    Mar 2012
    From
    London, UK
    Posts
    107
    Thanks
    37

    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.$
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member Sylvia104's Avatar
    Joined
    Mar 2012
    From
    London, UK
    Posts
    107
    Thanks
    37

    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.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member Sylvia104's Avatar
    Joined
    Mar 2012
    From
    London, UK
    Posts
    107
    Thanks
    37

    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.
    Last edited by Sylvia104; Apr 16th 2012 at 05:35 AM.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member Sylvia104's Avatar
    Joined
    Mar 2012
    From
    London, UK
    Posts
    107
    Thanks
    37

    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.


    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?

    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.$
    Last edited by Sylvia104; Apr 16th 2012 at 06:01 AM.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Member Sylvia104's Avatar
    Joined
    Mar 2012
    From
    London, UK
    Posts
    107
    Thanks
    37

    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.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,546
    Thanks
    842

    Re: Using group theory to prove results in number theory

    Quote Originally Posted by Sylvia104 View Post
    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$

    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.
    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).
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Textbooks on Galois Theory and Algebraic Number Theory
    Posted in the Advanced Algebra Forum
    Replies: 3
    Last Post: Jul 8th 2011, 06:09 PM
  2. Replies: 1
    Last Post: Feb 2nd 2011, 08:29 AM
  3. Replies: 1
    Last Post: Nov 4th 2009, 09:52 AM
  4. Quick questions on Group Theory - Cosets / Normal Group
    Posted in the Advanced Algebra Forum
    Replies: 3
    Last Post: Oct 16th 2009, 08:39 AM
  5. Group Theory - Sylow Theory and simple groups
    Posted in the Advanced Algebra Forum
    Replies: 16
    Last Post: May 16th 2009, 11:10 AM

Search Tags


/mathhelpforum @mathhelpforum