order of an element
(another Prime Pages' Glossary entries)
The Prime Glossary
Glossary: Prime Pages: Top 5000:
GIMPS has discovered a new largest known prime number: 282589933-1 (24,862,048 digits)

In a group (a special set with an operation on it like addition or multiplication), elements have orders.  Usually, on these pages, the group is the set of non-zero remainders modulo a prime and the order of a modulo p then is the least positive integer n such that an = 1 (mod p).

For example, let us use a=3 and p=7.  Look at the powers of 3 modulo 7:

31 = 3, 32 = 2, 33 = 6, 34 = 4, 35 = 5, 36 = 1
The order of 3 modulo 7 is 6.  The order of 2 modulo 7 is 3.  The order of 6 modulo 7 is 2.

When working modulo a prime, the set of non-zero remainders form a multiplicative group.  This is not true modulo a compositeFermat's Theorem tells us the order of a non-zero element modulo a prime divides the prime minus one.  Euler's theorem gives us a similar result for composites.

Chris K. Caldwell © 1999-2020 (all rights reserved)