Remainder when 4^1000 is divided by 7

Step by step

The question

Question: find 4¹⁰⁰⁰ mod 7.

4 to the power 1000 has 603 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 4.

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

4 to the 1 is 4.

Then 4 times 4 is 16.

16 mod 7 is 2.

And so on.

2 Find the pattern

At k = 4 we are back to 4.

From here everything repeats.

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

3 Where 1000 lands

1000 divided by 3: 333 full patterns, and 1 left over.

Careful!

The pattern is all we need.

The full number is far too big.

So 4 to the 1000 is like k = 1.

So 4¹⁰⁰⁰ mod 7 is 4.

4 Check

A computer can work out all 603 digits: 114813, and so on, 9376.

Divided by 7, it leaves 4, the same as our pattern.

Right!

Let's look back.

First: small powers first.

Then: find the pattern.

Then: where 1000 lands.

Last: check.