Multiplicative order

In number theory, given an integer a and a positive integer n with gcd(a,n) = 1, the multiplicative order of a modulo n is the smallest positive integer k with

a^k ≡ 1 (modulo n). Number theory is the branch of Pure mathematics concerned with the properties of Numbers in general and Integers in particular as well as the wider classes The integers (from the Latin integer, literally "untouched" hence "whole" the word entire comes from the same origin but via French In Mathematics, the greatest common divisor (gcd, sometimes known as the greatest common factor (gcf or highest common factor (hcf, of two non-zero In Mathematics, modular arithmetic (sometimes called modulo arithmetic, or clock arithmetic) is a system of Arithmetic for Integers

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

For example, to determine the multiplicative order of 4 modulo 7, we compute 4² = 16 ≡ 2 (modulo 7) and 4³ ≡ 4×2 = 8 ≡ 1 (modulo 7), so ord₇(4) = 3.

Without knowledge that we are working in a finite group, 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 there must be two powers, say s and t, such that a^s ≡ a^t module n. Since a and n are coprime, this implies that a^|s-t| ≡ 1 modulo n. In Mathematics, the Integers a and b are said to be coprime or relatively prime if they have no common factor other than

The concept of multiplicative order is a special case of the order of group elements. In Group theory, a branch of Mathematics, the term order is used in two closely related senses the order of a group is The multiplicative order of a number a modulo n is the order of a in the multiplicative group whose elements are the residues modulo n of the numbers coprime to n, and whose group operation is multiplication modulo n. In Modular arithmetic the set of Congruence classes Relatively prime to the modulus n form a group under multiplication called the multiplicative This is the group of units of the ring Z_n; it has φ(n) elements, φ being Euler's totient function, and is denoted as U(n) or U(Z_n). In Mathematics, a unit in a ( Unital) ring R is an invertible element of R, i In Mathematics, a ring is an Algebraic structure which generalizes the algebraic properties of the Integers though the rational, real 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

As a consequence of Lagrange's theorem, ord_na always divides φ(n). Lagrange's theorem, in the Mathematics of Group theory, states that for any Finite group G, the order (number of elements of In Mathematics, a divisor of an Integer n, also called a factor of n, is an integer which evenly divides n without If ord_n a is actually equal to φ(n) and therefore as large as possible, then a is called a 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 This means that the group U(n) is cyclic and the residue class of a generates it. In Group theory, a cyclic group or monogenous group is a group that can be generated by a single element in the sense that the group has an

See also