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

### 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

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.
```
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