In number theory

Number theory

Number theory is a branch of pure mathematics devoted primarily to the study of the integers. Number theorists study prime numbers as well...

, given an integer

Integer

The integers are formed by the natural numbers together with the negatives of the non-zero natural numbers .They are known as Positive and Negative Integers respectively...

 a and a positive integer n with gcd

Greatest common divisor

In mathematics, the greatest common divisor , also known as the greatest common factor , or highest common factor , of two or more non-zero integers, is the largest positive integer that divides the numbers without a remainder.For example, the GCD of 8 and 12 is 4.This notion can be extended to...

(a,n) = 1, the multiplicative order of a modulo n is the smallest positive integer k with

a^k ≡ 1 (mod

Modular arithmetic

In mathematics, modular arithmetic is a system of arithmetic for integers, where numbers "wrap around" after they reach a certain value—the modulus....

 n).

The order of a modulo n is usually written ord_n(a), or O_n(a).

Example

To determine the multiplicative order of 4 modulo 7, we compute 4² = 16 ≡ 2 (mod 7) and 4³ = 64 ≡ 1 (mod 7), so ord₇(4) = 3.

Properties

Even without knowledge that we are working in the multiplicative group of integers modulo n

Multiplicative group of integers modulo n

In modular arithmetic the set of congruence classes relatively prime to the modulus n form a group under multiplication called the multiplicative group of integers modulo n. It is also called the group of primitive residue classes modulo n. In the theory of rings, a branch of abstract algebra, it...

, we can show that a actually has an order by noting that the powers of a can only take a finite number of different values modulo n, so according to the pigeonhole principle there must be two powers, say s and t and without loss of generality

Without loss of generality

Without loss of generality is a frequently used expression in mathematics...

 s>t, such that a^s ≡ a^t (mod n). Since a and n are coprime

Coprime

In number theory, a branch of mathematics, two integers a and b are said to be coprime or relatively prime if the only positive integer that evenly divides both of them is 1. This is the same thing as their greatest common divisor being 1...

, this implies that a has an inverse element a^-1 and we can multiply both sides of the congruence with a^-t, yielding a^s-t ≡ 1 (mod n).

The concept of multiplicative order is a special case of the order of group elements

Order (group theory)

In group theory, a branch of mathematics, the term order is used in two closely related senses:* The order of a group is its cardinality, i.e., the number of its elements....

. The multiplicative order of a number a modulo n is the order of a in the multiplicative group

Multiplicative group of integers modulo n

In modular arithmetic the set of congruence classes relatively prime to the modulus n form a group under multiplication called the multiplicative group of integers modulo n. It is also called the group of primitive residue classes modulo n. In the theory of rings, a branch of abstract algebra, it...

 whose elements are the residues modulo n of the numbers coprime to n, and whose group operation is multiplication modulo n. This is the group of units of the ring

Ring (mathematics)

In mathematics, a ring is an algebraic structure consisting of a set together with two binary operations usually called addition and multiplication, where the set is an abelian group under addition and a semigroup under multiplication such that multiplication distributes over addition...

 Z_n; it has φ(n) elements, φ being Euler's totient function

Euler's totient function

In number theory, the totient \varphi of a positive integer n is defined to be the number of positive integers less than or equal to n that are coprime to n In number theory, the totient \varphi(n) of a positive integer n is defined to be the number of positive integers less than or equal to n that...

, and is denoted as U(n) or U(Z_n).

As a consequence of Lagrange's theorem

Lagrange's theorem (group theory)

Lagrange's theorem, in the mathematics of group theory, states that for any finite group G, the order of every subgroup H of G divides the order of G. The theorem is named after Joseph Lagrange....

, ord_n(a) always divides

Divisor

In mathematics, a divisor of an integer n, also called a factor of n, is an integer which divides n without leaving a remainder.-Explanation:...

 φ(n). If ord_n a is actually equal to φ(n) and therefore as large as possible, then a is called a primitive root

Primitive root modulo n

In modular arithmetic, a branch of number theory, a primitive root modulo n is any number g with the property that any number coprime to n is congruent to a power of g modulo n. In other words, g is a generator of the multiplicative group of integers modulo n...

 modulo n. This means that the group U(n) is cyclic

Cyclic group

In group theory, a cyclic group is a group that can be generated by a single element, in the sense that the group has an element g such that, when written multiplicatively, every element of the group is a power of g .-Definition:A group G is called cyclic if there exists an element g...

 and the residue class of a generates it.

The order ord_n a also divides

Divisor

In mathematics, a divisor of an integer n, also called a factor of n, is an integer which divides n without leaving a remainder.-Explanation:...

 λ(n), a value of the Carmichael function, which is an even stronger statement than the divisibility of φ(n).