Results 1 to 7 of 7

Math Help - 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 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.
    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 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.
    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) 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.
    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 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.
    Last edited by Sylvia104; April 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 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.
    Last edited by Sylvia104; April 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 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.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,150
    Thanks
    591

    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 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).
    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: July 8th 2011, 06:09 PM
  2. Replies: 1
    Last Post: February 2nd 2011, 08:29 AM
  3. Replies: 1
    Last Post: November 4th 2009, 09:52 AM
  4. Quick questions on Group Theory - Cosets / Normal Group
    Posted in the Advanced Algebra Forum
    Replies: 3
    Last Post: October 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