My brother does some kind of maths challenge through his school. Sometimes I get a little bit involved… this time I was asked how to find the last 3 digits of a large number that won’t fit on the calculator: 3^1994. I wasn’t sure how to go about this but after some reading I found that the Binomial Theorem was a good way to go about it.
Method 1/3: Binomial Expansion [EDIT: The last method is probably the easiest to understand]
The binomial theorem tells us how to expand the sum of an algebraic expression that has been raised to a power -the one most people are familiar with is (x + y)^2 = x^2 + 2xy + y^2. I have written the binomial theorem out up to a power of seven (below).
Figure 1 – The Binomial Expansion to a power of seven arranged in a triangle fashion.
The reason I have arranged these equations into a triangle shape is to highlight its connection to something known as Pascal’s Triangle (below). Pascal’s triangle starts with a ‘1’ and continues down in a triangle shape where each subsequent number is the sum of those above it. If you compare Pascal’s triangle to the coefficients in the image above you will notice a similarity.
Figure 2 – Pascal’s Triangle.
So, by now you may be wandering how all this will help us in finding the last 3 digits of 3^1994. If we look at the last line in Figure 1 we can notice the exponents of y go: y^0, y^1, y^2, y^3 … all the way to y^7. What if y=10, then we have: 1, 10, 100, … 10000000. This is the trick we will use as any whole number multiplied by 10^n where n>3 is going to end in at least 3 zeros! Since we are working in mod 1000 these terms will not affect our answer and they can all be cancelled.

But how are we going to write 3^1994 so we can use the Binomial Theorem? 3 can become a 9 by squaring and then 9 = 10-1:

3^1994 = 3^(2*997) = 9^(997) = (10 – 1)^997

Expanding using the Binomial theorem gives the following:

Figure 3 – Expanding our expression using the Binomial Theorem.

The only thing we now need to do is find the coefficients: C0, C1, C2. It would take a long time trying to find these by drawing out Pascal’s Triangle… luckily there is another way: using the combinational interpretation.
We can think about a combination like this: “If I have ‘n’ people and have to pick ‘r’ people, in how many ways can this be done?” If we have 3 people (go to the 4th row in Pascals triangle) and need to select 1 person (go to the second number in that row) we have 3 choices (looking at Pascal’s triangle we see that there is indeed a 3 in that position).
On the calculator we can use the nCr button to calculate combinations for us. Writing out the line of Pascal’s Triangle for the power of 997 gives the following:

The coefficients for a power of 997 written in combinational form.
Entering these into my calculator gave the following:
C0 = 1
C1 = 997
C2 = 496,506

Substituting these into the equation we ended up with in Figure 3 gives the following:
== -1 + (10)(997) – (100)(496,506) [mod 1000]
== -1 + 970 – 600 [mod 1000] (this step is explained in more detail below if you find it confusing)
== 369

So there we go, the last three digits of 3^1994 are {3,6,9}.

To check my answer I simply entered 3^1994 into Wolframalpha… perhaps that would be a simpler way:

Here’s what Wolframalpha gives me.



The next part of the question was the last 3 digits of 7^1994. I thought this would pan out in a similar way: write it as (10 – 3)^1994 and then do a similar thing (i.e. expand using binomial theorem and only keep the first few terms). 
Using the method above here;s what I ended up with:


 (-3)^1994 + 1994(-3)^1993(10) + {1994C2}(-3)^1992(100) (mod 1000)

This can be simplified by removing the -ve’s on the 3’s:
(3)^1994 1994(3)^1993(10) + {1994C2}(3)^1992(100) (mod 1000)

Using a calculator to work out the combination:
(3)^1994 – 1994(3)^1993(10) + (1987021)(3)^1992(100) (mod 1000)

Now note that we have a similar question as the first part: “How to calculate the 3^1994?’
(3)^19941994(3)^1993(10) + (1987021)(3)^1992(100) (mod 1000)

Luckily we have just calculated  the last three digits of (3)^1994 (mod 1000) so we can substitute this in:
(369)1994(369)(10) + (1987021)(369)(100) (mod 1000)

Simplifying:
(369) – (7357860) + (73321074900)
== 369 – 860 + 900
== 409




After checking this I found I had the wrong answer… Hmmm, so what went wrong? It turns out I made a very silly mistake and forgot to substitute the correct numbers for the other powers of three:
(3)^1994 == 369
(3)^1993 == 369/3 == 123
(3)^1992 == 369/3/3 == 41

Substituting the correct numbers:
(369)1994(123)(10) + (1987021)(41)(100) (mod 1000)

Simplifying:
(369) – (2452620) + (8146786100)
== 369 – 620 + 100
== -151
== 849
Checking on Wolframalpha:
***
I thought I’d write a little more about the second last line (and some ways you can reduce to 849 – I have included a four digit substitution for 3^1994, etc.):
== (9369)1994(3123)(10) + (1987021)(1041)(100) (mod 1000)

The first thing to do is realise that the sign is going to be +ve so we want to end up with a +ve answer, but it would also be nice not to have to enter the whole thing… It turns out we don’t really need to. Since we are mod 1000 we can get rid of all the thousands:
== (369)994(123)(10) + (021)(041)(100) (mod 1000)

This will give the correct answer:
==  – 1 136 151
== -151
== 1000 – 151
== 849

Alternatively you can simplify each section of the expression before entering on the calculator:
== (369)994(123)(10) + (021)(041)(100) (mod 1000)
== (369)1222620 + 86100 (mod 1000)NOTE THE TRAILING ZEROS IN THIS LINE!
== 369 – 620 + 100
== -151
== 849

However we can simply even further before calculating (from the observation in capitals above). Since we are multiplying the second part by 10, we only need the last two digits, and similarly only the last one for the third part:
== (369)94(23)(10) + (1)(1)(100) (mod 1000)
== (369)94(23)(10) + (100) (mod 1000)
== – 21 151
== -151
== 849

***

Another thing which might not be so obvious is if we have something like 65426677^1222, we can reduce it to 677^1222 if we are working in mod 1000:
65426677^1222 = (65426000 + 677)^1222

If we were to expand using the Binomial Theorem we would get:
(C0)(677^1222) + (C1)(677^1221)(65426000) + …

By inspection we can see that all the terms except the first one will end in at least three zeros. Therefore (using the face C0 is always equal to one):
65426677^1222 == (677^1222) [mod 1000]

I actually haven’t thought of a way to break 677^1222 down further… let me know if you do!
[EDIT: Here are some possible ways]

Method 2/3: Euler’s Method

Was doing some more reading and came across a way involving good old Euler. I have a shallow understanding of this method and will first explain the overview.

Say we again have 3^1994 and want to find the last two digits. Euler’s method finds a power of three that ends in 01 – in this case 3^40 ends in 01. We then divide 1994 by 40 and find a quotient of 49 and a remainder of 34. This means we can write 3^1994 as:

3^1994 = [(3^40)^49][3^34]

Since we know 3^40 ends in 01 and we are working in mod 100 we have:
3^1994 = [(1)^49][3^34] = 3^34

Now the next little trick I have picked up is to find a power that will come close to our modulus. By this I mean that 3^4 = 81 is close to 100. And then we can say that 81 == (-19) {mod 100}. So again expanding using the quotient and remainder we have:
3^34 = [(3^4)^8][3^2] = [(81)^8][3^2] = [(-19)^8][3^2] = [(19)^8][3^2]
= [16,983,563,041][9] == (41)(9) = 369 == 69

Now I don’t fully understand how this works but we start with:
    10 = (2)    (5)
  100 = (2^2)(5^2)
1000 = (2^3)(5^3)

We can then convert these to what power we should use:
    ø(10) =  10    (1 – 1/2)(1 – 1/5) = 4
  ø(100) =  100  (1 – 1/2)(1 – 1/5) = 40
ø(1000) =  1000(1 – 1/2)(1 – 1/5) = 400
Where ø is the totient function (an augmentation of Fermat’s theorem).

The idea behind this is that for 3^1994:
The units repeat every 4,
The tens repeat every 40,
the hundreds repeat every 400.
So for the above example we used 40 as we were working in mod 100, if we wanted the last three digits we would have selected 400. Lets see how I go with the last 3 digits of 7^1994

So first I will divide 1994 by 400 to get a quotient of 4 and a remainder of 394, so:
7^1994 = [(7^40)^4][7^394] == 7^394 {mod 1000}

So the problem is now reduced to finding the last three digits of 7^394… but how to do this?

I though “394 is close to 400”:
7^394 = 7^(400 – 6) = 7^(400) / 7^(6) = 1/(7^6) [mod 1000] = 1/649

But didn’t know how to proceed from there…
[EDIT: Here is an easy way that is probably the easiest to understand out of all three methods]

Method 3/3: Successive Squaring

The alternate way I could think to reduce this was using successive squaring, So writing 394 as its factors:

7^1    =                  7
7^2    =  6^2   =   49
7^4    = 49^2  = 401 [mod 1000]
7^8    = 401^2 = 801
7^16  = 801^2 = 601
7^32  =            = 201
7^64  =            = 401
7^128 =           = 801 (note that it starts repeating here)
7^256 =           = 601

Since 394 = 256 + 128 + 8 + 2:

7^394 = (7^256)(7^128)(7^8)(7^2) = (601)(801)(801)(49) = 18,894,507,849 = 849

This is probably the simplest method from a conceptual standpoint.

Advertisements