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