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,

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
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
Math Forum Home || Math Library || Quick Reference || Math Forum Search