Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Order of a mod m & quadratic residues

  1. Mar 1, 2010 #1
    "order" of a mod m & quadratic residues

    1) Definition: Let m denote a positive integer and a any integer such that gcd(a,m)=1. Let h be the smallest positive integer such that ah≡ 1 (mod m). Then h is called the order of a modulo m. (notation: h=em(a) )
    ================
    Now, why do we need to assume gcd(a,m)=1 in this definition of order? Is it true that if gcd(a,m)≠1, then the order em(a) is undefined? Why or why not? I can't figure this out. I know that the multiplicative inverse of a mod m exists <=> gcd(a,m)=1, but I don't see the connection...




    2) Definition: For all a such that gcd(a,m)=1, a is called a quadratic residue modulo m if the congruence x2 ≡ a (mod m) has a solution. If it has no solution, then a is called a quadratic nonresidue modulo m.
    ====================
    Once again, why is the assumption gcd(a,m)=1 needed? What happens when gcd(a,m)≠1?


    May someone explain, please?
    Thanks a million!
     
  2. jcsd
  3. Mar 1, 2010 #2
    Re: "order" of a mod m & quadratic residues

    (1) Z/pZ is a field if and only if p .........?
    If gcd (a,m) is not 1, then can you always find such an h?

    (2) Look up some stuff on quadratic residues (for example, Quadratic Reciprocity Theorem).
     
  4. Mar 1, 2010 #3
    Re: "order" of a mod m & quadratic residues

    1) Hi, I'm sorry but I have no background in abstract algebra. Can you explain it in simpler terms if possible?
    Is it related to the theorem "the multiplicative inverse of a mod m exists <=> gcd(a,m)=1"? If so, how?


    2) Why do we need to assume gcd(a,m)=1 in the first place even before defining the term "quadratic residue"? Why can't we allow the case gcd(a,m)>1?

    thanks.
     
  5. Mar 1, 2010 #4
    Re: "order" of a mod m & quadratic residues

    (1) Yes, I assumed you have considered the set Zn = {0, 1, ..., n-1}, where arithmetic is done modulo n. When is this set a group under multiplication? If you don't know what that means - when does there exist a multiplicative inverse for an element in Zn? When will all elements of Zn be invertible?

    You have identified an important theorem.
    If the order is defined as h, ah = 1, then does it follow that a is invertible under multiplication? What is ah-1?

    (2) Quadratic residues may be defined without this condition. However, this condition becomes important in lots of the critical work for this topic, so it can be thought to naturally be in this form - which is why I asked you to consider some theorems on this topic (see law of Quadratic Reciprocity).
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Order of a mod m & quadratic residues
Loading...