- #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 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^{2}≡ 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!