# order of an element

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

*a*

^{n}≡ 1 (mod

*p*).

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

3^{1}≡ 3, 3^{2}≡ 2, 3^{3}≡ 6, 3^{4}≡ 4, 3^{5}≡ 5, 3^{6}≡ 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 composite. Fermat'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.

Printed from the PrimePages <t5k.org> © Reginald McLean.