Calculate 3^100 mod 5

Step by step

The question

Question: find 3¹⁰⁰ mod 5.

3 to the power 100 has 48 digits.

Too big to work out by hand.

1 Small powers first

Let's make a table of small powers.

Each one is the one before times 3.

We only keep the remainder: the big part never matters.

3 to the 1 is 3.

Then 3 times 3 is 9.

9 mod 5 is 4.

And so on.

2 Find the pattern

At k = 5 we are back to 3.

From here everything repeats.

So the pattern 3, 4, 2, 1 repeats every 4 powers.

3 Where 100 lands

100 divided by 4: 25 full patterns, and 0 left over.

Careful!

Nothing left over means we end at the end of a pattern: the same place as k = 4.

So 3 to the 100 is like k = 4: the last one of the pattern.

So 3¹⁰⁰ mod 5 is 1.

4 Check

A computer can work out all 48 digits: 515377, and so on, 2001.

Divided by 5, it leaves 1, the same as our pattern.

Right!

Let's look back.

First: small powers first.

Then: find the pattern.

Then: where 100 lands.

Last: check.