Calculate 3^200 mod 13

Step by step

The question

Question: find 3²⁰⁰ mod 13.

3 to the power 200 has 96 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 13 is 9.

And so on.

2 Find the pattern

At k = 4 we are back to 3.

From here everything repeats.

So the pattern 3, 9, 1 repeats every 3 powers.

3 Where 200 lands

200 divided by 3: 66 full patterns, and 2 left over.

Careful!

The pattern is all we need.

The full number is far too big.

So 3 to the 200 is like k = 2.

So 3²⁰⁰ mod 13 is 9.

4 Check

A computer can work out all 96 digits: 265613, and so on, 4001.

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

Right!

Let's look back.

First: small powers first.

Then: find the pattern.

Then: where 200 lands.

Last: check.