Associated Topics || Dr. Math Home || Search Dr. Math

### Multiplicative Order

```
Date: 08/13/99 at 04:01:25
From: Mee
Subject: Multiplicative orders and modulo

I'm a Grade 11 Math student doing a little project on card shuffling,
and have come upon this pattern of "multiplicative order of 2 mod
2n+1" (taken from the book). I don't know what that means.

I have come across mods before in trying to solve a particular
problem, so it looks right. I want to know what a multiplicative order
is IN SIMPLE TERMS! I know it has something to do with powers and
being congruent, but I do not understand at all.

Also, isn't 2 mod 2n+1 always going to be 1? (I am very confused, as
this is a different way of writing mods than we have used in class...)

Can you help? I really need to know this to solve my problem.

Thank you very much,
Melinda
```

```
Date: 08/13/99 at 11:38:48
From: Doctor Rob
Subject: Re: Multiplicative orders and modulo

Thanks for writing to Ask Dr. Math.

The multiplicative order of any x modulo any modulus m is defined to
be the smallest positive integer n such that x^n = 1 (mod m), that is,
the smallest power to which x must be raised to leave a remainder of 1
when divided by m.

Example: The multiplicative order of 2 modulo 7 is 3, because

2^1 = 2 (mod 7),
2^2 = 4 (mod 7),
2^3 = 8 = 1 (mod 7).

Example: The multiplicative order of 2 modulo 11 is 10, because none
of 2^1, 2^2, ..., 2^9 are congruent to 1 (mod 11), but

2^10 = 1024 = 11*93+1 = 1 (mod 11)

Here are a couple of useful facts about the multiplicative order. It
is always smaller than the modulus. If the modulus m is prime, it is a
divisor of m-1.

When you say, "isn't 2 mod 2n+1 always going to be 1?" I think you are
confused as to which of the two numbers is the modulus. It is true
that 2*n+1 = 1 (mod 2), but not true that 2 = 1 (mod 2*n+1), (unless
n = 0), and it is the latter situation that is applicable to your
project.

- Doctor Rob, The Math Forum
http://mathforum.org/dr.math/
```
Associated Topics:
High School Number Theory

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search