Calculate 2^35 mod 9

Step by step

The question

Question: find 2³⁵ mod 9.

2 to the power 35 has 11 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 2.

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

2 to the 1 is 2.

Then 2 times 2 is 4.

4 mod 9 is 4.

And so on.

2 Find the pattern

At k = 7 we are back to 2.

From here everything repeats.

So the pattern 2, 4, 8, 7, 5, 1 repeats every 6 powers.

3 Where 35 lands

35 divided by 6: 5 full patterns, and 5 left over.

Careful!

The pattern is all we need.

The full number is far too big.

So 2 to the 35 is like k = 5.

So 2³⁵ mod 9 is 5.

4 Check

A computer can work out all 11 digits: 34359738368.

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

Right!

Let's look back.

First: small powers first.

Then: find the pattern.

Then: where 35 lands.

Last: check.