Order of an Element

Number Theory · Axiom Academy

Understanding multiplicative order in modular arithmetic In other words, the order tells us the smallest number of times we need to multiply a by itself to get 1 (mod n ). Key requirement: We require gcd( a , n ) = 1, meaning a and n must be coprime. This ensures that a has a multiplicative inverse modulo n . This means the order must be a divisor of φ( n ), where φ is Euler's totient function. Why is this true? By Euler's theorem, we know that a φ( n ) ≡ 1 (mod n ). Since ord n ( a ) is the smallest positive power that gives 1, it must divide φ( n ). In particular, a m ≡ 1 (mod n ) if and only if ord n ( a ) divides m . Solution: We need to find the smallest positive k such that 3 k ≡ 1 (mod 7). Let's compute successive powers of 3 modulo 7: Verification: Note that φ(7) = 6, and indeed 6 divides 6, confirming our property that ord n ( a ) | φ( n ). 4. Example: Finding ord 13 (2) Strategy: Since φ(13) = 12, we know ord 13 (2) must divide 12. The divisors of 12 are: 1, 2, 3, 4, 6, 12. We can test these divisors in order: 2 6 ≡ 64 ≡ 12 ≡ -1 (mod 13) - not 1 2 12 ≡ (2 6 ) 2 ≡ (-1) 2 ≡ 1 (mod 13) Important note: Since ord 13 (2) = φ(13) = 12, we say that 2 is a primitive root modulo 13. This means the powers of 2 generate all non-zero elements modulo 13. The order of a mod n is the smallest k such that a k ≡ 1 (mod n ) The order always divides φ( n ), limiting possible values To find the order efficiently, test divisors of φ( n ) in ascending order

This is the written version of the interactive lesson above. See the full Number Theory course.