display | more...

Additive order

A ring whose operations are "multiplication" and "addition" can have additive orders and multiplicative orders for each of its elements. The additive order of a given element r in a ring R is the number of times n which r must be 'added' to itself (under the ring's "additive" operation) to get the zero of R. In basic mathematical notation: n ∈ N such that n*r = 0R. (Note: even though integers and ring elements are being mixed/multiplied together, we define this kind of 'multiplication' as 'multiple additions', so something like 3*r is understood to mean r+r+r under the ring's addition operation.) If no finite n exists such that n*r = 0R, we let n = ∞.

In the context of the integers

The set of integers form a ring (in fact, an integral domain) over the multiplication and addition operations. The additive order of any given integer within the context of the integers is ∞, so we usually talk about the additive order of integers modulo a specifc integer.

Given integers a and n (n positive), the additive order of a mod n is the smallest positive integer m such that m*a=0(mod n). In fact, the additive order m of a mod n is always m=n/gcd(a,n).

Proof (m=n/gcd(a,n) is the additive order of a mod n):

Let a and n be integers, n positive. Let m=n/gcd(a,n). Then m*a=a*n/gcd(a,n)=n*(a/gcd(a,n))=0(mod n) (since gcd(a,n) divides a).

Let a and n be integers, n positive. Notice that n*a=0(mod n), since n|n*a. But n|n*(a/gcd(a,n)) as well, which is the same as saying n|(n/gcd(a,n))*a. Then d=gcd(a,n) is the greatest integer such that d|a and d|n, so n/gcd(a,n) is the smallest number with the property n|n*a/gcd(a,n). Thus m=n/gcd(a,n) is the additive order of a mod n.