"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!