Step by step
The question
Question: find 3⁴⁵ mod 7.
3 to the power 45 has 22 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 7 is 2.
And so on.
2 Find the pattern
At k = 7 we are back to 3.
From here everything repeats.
So the pattern 3, 2, 6, 4, 5, 1 repeats every 6 powers.
3 Where 45 lands
45 divided by 6: 7 full patterns, and 3 left over.
Careful!
The pattern is all we need.
The full number is far too big.
So 3 to the 45 is like k = 3.
So 3⁴⁵ mod 7 is 6.
4 Check
A computer can work out all 22 digits: 295431, and so on, 8643.
Divided by 7, it leaves 6, the same as our pattern.
Right!
Let's look back.
First: small powers first.
Then: find the pattern.
Then: where 45 lands.
Last: check.