Order of a mod m & quadratic residues

  • Thread starter kingwinner
  • Start date
  • Tags
    Quadratic
In summary, the "order" of a mod m is defined as the smallest positive integer h such that ah ≡ 1 (mod m). This definition requires gcd(a,m)=1. Without this condition, the order is undefined. Similarly, the definition of quadratic residues and nonresidues also requires gcd(a,m)=1. This condition is necessary for many theorems and critical work in this topic, such as the law of Quadratic Reciprocity. In simpler terms, this condition ensures that the multiplicative inverse of a mod m exists, which is essential for various calculations and proofs involving quadratic residues.
  • #1
kingwinner
1,270
0
"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!
 
Physics news on Phys.org
  • #2


(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).
 
  • #3


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.
 
  • #4


(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).
 
  • #5



1) The assumption of gcd(a,m)=1 is necessary in the definition of order because it ensures that a has a multiplicative inverse modulo m. This means that there exists an integer b such that ab≡ 1 (mod m). If gcd(a,m)≠1, then a does not have a multiplicative inverse and therefore the congruence ah≡ 1 (mod m) may not have a solution. In this case, the order em(a) would be undefined. The connection between gcd(a,m)=1 and the existence of a multiplicative inverse is crucial in defining the order of a modulo m.

2) Similarly, the assumption of gcd(a,m)=1 is needed in the definition of quadratic residues because it ensures that a has a multiplicative inverse modulo m. If gcd(a,m)≠1, then a does not have a multiplicative inverse and therefore the congruence x2 ≡ a (mod m) may not have a solution. In this case, a would not be considered a quadratic residue. The existence of a multiplicative inverse is necessary in solving the congruence and determining if a is a quadratic residue or not.
 

1. What is the order of a mod m?

The order of a mod m refers to the smallest positive integer k such that a^k ≡ 1 (mod m), where a and m are integers. In other words, it is the number of times a must be multiplied by itself to get a remainder of 1 when divided by m.

2. How is the order of a mod m calculated?

The order of a mod m can be calculated using Euler's totient function, which is defined as φ(m) = m * (1 - 1/p1) * (1 - 1/p2) * ... * (1 - 1/pn), where p1, p2, ..., pn are the distinct prime factors of m. The order k is then the smallest positive integer for which a^k ≡ 1 (mod m).

3. What are quadratic residues?

Quadratic residues are numbers that have a square root modulo some integer m. In other words, they are numbers that when squared and divided by m, leave a remainder of 1.

4. How are quadratic residues related to the order of a mod m?

The number of quadratic residues modulo m is equal to half the order of a mod m. This is known as the Quadratic Reciprocity Law.

5. What is the significance of the order of a mod m in cryptography?

The order of a mod m is an important concept in cryptography as it is used in the computation of discrete logarithms, which are essential in many public-key cryptographic systems. It also plays a role in determining the security of certain cryptographic algorithms.

Similar threads

  • Linear and Abstract Algebra
Replies
3
Views
1K
  • Linear and Abstract Algebra
Replies
2
Views
1K
  • Calculus and Beyond Homework Help
Replies
2
Views
1K
  • Calculus and Beyond Homework Help
Replies
2
Views
983
  • Linear and Abstract Algebra
Replies
4
Views
3K
  • General Math
Replies
5
Views
2K
Replies
10
Views
5K
  • Linear and Abstract Algebra
Replies
1
Views
2K
  • Calculus and Beyond Homework Help
Replies
11
Views
1K
  • Linear and Abstract Algebra
Replies
2
Views
1K
Back
Top