properties of the multiplicative order of an integer


Let m>1 be an integer and let a be another integer relatively prime to m. The order of a modulo m (or the multiplicative orderMathworldPlanetmath of amodm) is the smallest positive integer n such that an1modm. The order is sometimes denoted by orda or ordma.


Let m be a positive integer and suppose that (a,m)=1.

  1. 1.

    as1modm if and only if orda divides s. In particular, orda divides ϕ(m), where ϕ is the Euler phi function.

  2. 2.

    asatmodm if and only if stmodorda.

  3. 3.

    If orda=d then ordak=dgcd(k,d) for any k1.

  4. 4.

    If orda=d and e is a positive divisorMathworldPlanetmathPlanetmathPlanetmath of d then ad/e has exact order e.

  5. 5.

    Suppose orda=h and ordb=k with gcd(h,k)=1. Then ord(ab)=hk.

Title properties of the multiplicative order of an integer
Canonical name PropertiesOfTheMultiplicativeOrderOfAnInteger
Date of creation 2013-03-22 16:20:44
Last modified on 2013-03-22 16:20:44
Owner alozano (2414)
Last modified by alozano (2414)
Numerical id 4
Author alozano (2414)
Entry type Theorem
Classification msc 11-00
Classification msc 13M05
Classification msc 13-00