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

Using Modular Arithmetic to Find Remainders

```Date: 10/21/2004 at 11:19:02
From: Tahir
Subject: Finding remainders using mod

What is the remainder when 2^(2^405) is divided by 23?

I can't figure out a formula or a general method for solving problems
like these.  I solved it by making a chart of initial values and saw
that remainders of 2^(2^n) are the same for every n+10.  So 2^2^405 is
the same as 2^2^5 which is 12.

I obviously can't use this approach on an exam, so what is the proper
way to do this question?  Thanks.

```

```
Date: 10/21/2004 at 11:48:14
From: Doctor Vogler
Subject: Re: Finding remainders using mod

Hi Tahir,

Thanks for writing to Dr. Math.  First let's think about how we would
find

2^10000 mod 23.

Since 2^22 = 1 mod 23, by Fermat's Little Theorem, we would find

10000 mod 22

and then raise 2 to this power mod 23.

If that makes sense to you, then you can do the same thing with your
problem.  To find

2^(2^405) mod 23,

you need to find

2^405 mod 22.

Well, that's just another modular exponent problem!  So how do you
find 2^405 mod 22?  I would probably start by finding

2^405 mod 11

using Fermat's Theorem, and

2^405 mod 2

which is easy, and then put them together with the Chinese Remainder
Theorem.  That gives you the exponent

2^405 mod 22

and you raise 2 to that power mod 23.

Find the Monster Mod 11, Mod 2310
http://mathforum.org/library/drmath/view/62908.html

from our archives.

back and show me what you have been able to do, and I will try to
offer further suggestions.

- Doctor Vogler, The Math Forum
http://mathforum.org/dr.math/

```

```
Date: 10/21/2004 at 11:54:58
From: Tahir
Subject: Thank you (Finding remainders using mod)

Thank you. It is clear now. :)
```
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