Orders and quadratic residues · Definition

Multiplicative order

elementary number theoryorders and quadratic residues

Before you start you need to know

Many questions about powers in modular arithmetic reduce to knowing how many times a number must be raised before it returns to 1. This concept is the foundation of primitive roots.

Definition

The multiplicative order of \( a \) modulo \( n \), \( \operatorname{ord}_n(a) \), is the smallest positive exponent that returns \( a \) to the unit class modulo \( n \).

\[\operatorname{ord}_n(a)=\min\{k\ge 1: a^k\equiv 1 \pmod{n}\}\]

If \( \operatorname{ord}_n(a)=k \), then \( a^m \equiv 1 \pmod{n} \) if and only if \( k \mid m \). It follows that the order always divides \( \varphi(n) \), which is Euler's theorem seen through the order.

For \( n=7 \) and \( a=2 \), the powers are \( 2, 4, 1 \), so \( \operatorname{ord}_7(2)=3 \). This value is consistent with \( \varphi(7)=6 \), since 3 divides 6.

A typical mistake is to assume that the order of every \( a \) equals \( \varphi(n) \). The case \( \operatorname{ord}_7(2)=3 \) already disproves this, and the order does not exist when \( \gcd(a,n)>1 \).

Think about it

If \( \operatorname{ord}_n(a)=k \), which exponents \( m \) satisfy \( a^m \equiv 1 \pmod{n} \)?

Exactly the multiples of \( k \), that is, the \( m \) with \( k \mid m \).

Exercises 10

  1. What is the definition of the multiplicative order of \( a \) modulo \( n \)?
  2. What is \( \operatorname{ord}_5(4) \)?
  3. What condition must \( a \) satisfy for \( \operatorname{ord}_n(a) \) to exist?
  4. If \( \operatorname{ord}_n(a)=k \) and \( a^m \equiv 1 \pmod{n} \), what relation must hold?
  5. What is \( \operatorname{ord}_{10}(3) \)?
  6. Compute \( \operatorname{ord}_9(2) \).
  7. If \( \operatorname{ord}_{13}(a)=6 \), what is \( \operatorname{ord}_{13}(a^2) \)?
  8. How is \( \operatorname{ord}_n(a^{-1}) \) related to \( \operatorname{ord}_n(a) \), when \( a \) is invertible modulo \( n \)?
  9. It is claimed that \( \operatorname{ord}_7(a)=\operatorname{ord}_7(a^2) \) for every invertible \( a \). Which value of \( a \) disproves the claim?
  10. Compute \( \operatorname{ord}_{15}(2) \) step by step.

What comes next

References

  • David M. Burton, Elementary Number Theory, 7th edition, McGraw-Hill, 2011. cap. 8
  • Ivan Niven, Herbert S. Zuckerman, Hugh L. Montgomery, An Introduction to the Theory of Numbers, 5th edition, Wiley, 1991. cap. 2