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. :)
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.