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/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.