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.

See also

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

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