Order of a mod m & quadratic residues

[kingwinner]

"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 a^h≡ 1 (mod m). Then h is called the order of a modulo m. (notation: h=e_m(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 e_m(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 x² ≡ 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!

 

[VeeEight]

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

 

[kingwinner]

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.

 

[VeeEight]

(1) Yes, I assumed you have considered the set Z_n = {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 Z_n? When will all elements of Z_n be invertible?

You have identified an important theorem.
If the order is defined as h, a^h = 1, then does it follow that a is invertible under multiplication? What is a^h-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).

 

[blue_raver22]

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.