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/