**Method 1/3: Binomial Expansion****[EDIT: The last method is probably the easiest to understand]**

*Figure 1 – The Binomial Expansion to a power of seven arranged in a triangle fashion.*

*Figure 2 – Pascal’s Triangle.*

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

*Figure 3 – Expanding our expression using the Binomial Theorem.*

*The coefficients for a power of 997 written in combinational form.*

**C0 = 1**

**C1 = 997**

**C2 = 496,506**

**== -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**

*Here’s what Wolframalpha gives me.*

(-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)^1994 – 1994(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)

(369) – (2452620) + (8146786100)

== 369 – 620 + 100

== -151

== 849

*******

== (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.