Orders and quadratic residues

Concepts

• Multiplicative order 10 exercisesThe multiplicative order of a modulo n , ord_n(a) , is the smallest positive exponent that returns a to the unit class modulo n .
• Primitive root 10 exercisesA primitive root modulo n is an integer g whose multiplicative order modulo n equals φ(n), so that its powers run through all res…
• Quadratic residue 10 exercisesA quadratic residue modulo n is an integer a with gcd(a,n)=1 such that the congruence x² ≡ a (mod n) has a solution. If it has no…
• Legendre symbol 10 exercisesThe Legendre symbol ((a)/(p)) for an odd prime p and an integer a with p nmid a equals 1 if a is a quadratic residue modulo p, an…
• Euler's criterion 10 exercisesCriterion that decides whether an integer a is a quadratic residue modulo an odd prime p by means of a modular power.
• Law of quadratic reciprocity 10 exercisesThe law of quadratic reciprocity relates the Legendre symbols ((p)/(q)) and ((q)/(p)) for distinct odd primes p and q.