Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
Associated Topics || Dr. Math Home || Search Dr. Math
_____________________________________________

Calculating Large Exponentials with Modular Arithmetic

Date: 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
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-2013 The Math Forum
http://mathforum.org/dr.math/