Calculating Large Exponentials with Modular ArithmeticDate: 01/02/2005 at 01:01:22 From: srini Subject: Calculating exponentials What's the units digit of (33)^33 + (43)^43? I'd like to know the easiest way to arrive at the units digit without having to apply brute force. Is there a shortcut? Thanks, Srini Date: 01/02/2005 at 02:57:06 From: Doctor Luis Subject: Re: Calculating exponentials Hi Srini, I'm not sure if you're familiar with the congruence notation. If not, look at this page: http://mathworld.wolfram.com/Congruence.html Now, why is this useful? You'll note that the units digit is just the remainder when you divide by 10. Since modular arithmetic is very easy, that makes it simple to calculate large powers. For example, I'll calculate the units digit of 2^100 + 7^5. First, let's take care of the first term. We know the remainder when dividing 2 by 10 is....2. Let's just call it x for now. Next, we note that 100 is 10*10. x = 2 mod 10 x^10 = 2^10 mod 10 = 1024 mod 10 x^10 = 4 mod 10 x^100 = (x^10)^10 mod 10 = (4)^10 mod 10 = (2^10)^2 mod 10 = (4)^2 mod 10 = 16 mod 10 = 6 mod 10 so, since x = 2, we know 2^100 = 6 mod 10 Using the same reasoning for 7^5: y = 7 mod 10 y^2 = 7^2 mod 10 = 49 mod 10 = 9 mod 10 y^4 = (y^2)^2 mod 10 = (9)^2 mod 10 = 81 mod 10 = 1 mod 10 y^5 = y*y^4 mod 10 = 7 * 1 mod 10 = 7 mod 10 In other words, 7^5 = 7 mod 10 So, finally, we have 2^100 + 7^5 = 6 + 7 mod 10 = 13 mod 10 = 3 mod 10 That means that the units digit of 2^100 + 7^5 is just 3. By a brute force calculation (using a computer of course), 2^100 + 7^5 = 1267650600228229401496703222183 It worked! It's not quite a shortcut, but modular arithmetic is definitely much easier. This method should work even if you want to calculate the units digit of 2^1000000000000000001 + 1, which is doable if you're clever enough to setup the multiplications progressively. Got it? You should be able to apply it to your example now. I hope this helped! Let us know if you have any more questions. - Doctor Luis, The Math Forum http://mathforum.org/dr.math/ Date: 01/02/2005 at 13:46:10 From: srini Subject: Thank you (Calculating exponentials) Dr. Luis, Thanks a lot! Although I didn't understand congruence that well, I did understand your example. I've done mine based on your example, and got the same answer I did with brute force. Thanks again! - Srini |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994- The Math Forum at NCTM. All rights reserved.
http://mathforum.org/dr.math/