Find the Monster Mod 11, Mod 2310

Date: 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.