Find the Monster Mod 11, Mod 2310Date: 05/07/2003 at 15:50:46 From: Matt Subject: Modular Arithmetic Find an integer n between 0 and 2309 with the property that 34 10 10 10 = n (mod 2310) I do not know how to break the powers down to solve this problem. Date: 05/08/2003 at 22:28:04 From: Doctor Mitteldorf Subject: Re: Modular Arithmetic Dear Matt, The first thing to notice is that 2310 is 2*3*5*7*11. Once we figure out what "the monster" is modulo each of the factors, we'll be able to answer the question. Mod 2 and mod 5 are easy - the answer is 0. (Can you see why?) Mod 3 isn't much harder - after all, it's just 1 followed by a whole lot of zeros, so the the "casting out 9's" rule tells you that it's 1. This leaves 7 and 11. I'll give you a start, and then leave it to you. Suppose you want to know (10^34) mod 7. You know that 10 mod 7 = 3, so it's the same as (3^34) mod 7. But multiplying 3 by itself mod 7, we get the sequence 3,2,6,4,5,1,3,2,6, etc. All we need is the 34th number in this sequence, which is the same as the 4th number, since 34 mod 6 = 4. Hence (10^34) mod 7 = 4. Generalizing, we can find A^B mod 7 by using A to come up with a sequential ordering of the the numbers (1,2,3,4,5,6) and then using (B mod 6) to determine which number from this sequence is the answer. So to find (A^B mod 7), what we're really interested in is the exponent B mod 6. In our original problem, the exponent is 10^(10^34), which again is just 1 followed by a lot of zeros. 10^N mod 6 = 4, for any N. Hence 10^(10^N) = 4, since 4 is the 4th number in the sequence 3,2,6,4,5,1,... I'll leave it to you to find the monster mod 11, and then to combine your results mod 2, 3, 5, 7 and 11 to find the monster mod 2310. - Doctor Mitteldorf, The Math Forum http://mathforum.org/dr.math/ Date: 05/09/2003 at 08:31:46 From: Matt Subject: Thank you (Modular Arithmetic) Thanks for the help on this one. I liked how you called that thing "the monster" - it really made me laugh. :-) Thanks again. |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/