Order of a mod m & quadratic residues

  • Thread starter kingwinner
  • Start date
  • #1
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!
 

Answers and Replies

  • #2
614
0


(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,270
0


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
614
0


(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).
 

Related Threads on Order of a mod m & quadratic residues

  • Last Post
Replies
3
Views
3K
Replies
2
Views
912
Replies
1
Views
2K
  • Last Post
Replies
2
Views
4K
  • Last Post
Replies
5
Views
5K
  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
16
Views
4K
  • Last Post
Replies
1
Views
3K
Replies
1
Views
3K
Top