The Math Forum

Ask Dr. Math - Questions and Answers from our Archives
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 

  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.

See also

  Find the Monster Mod 11, Mod 2310 

from our archives.

If you have any questions about this or need more help, please write
back and show me what you have been able to do, and I will try to
offer further suggestions.

- Doctor Vogler, The Math Forum 

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

[Privacy Policy] [Terms of Use]

Math Forum Home || Math Library || Quick Reference || Math Forum Search

Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.