Step by step
The question
Question: find 4³⁰ mod 5.
4 to the power 30 has 19 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 5 is 1.
And so on.
2 Find the pattern
At k = 3 we are back to 4.
From here everything repeats.
So the pattern 4, 1 repeats every 2 powers.
3 Where 30 lands
30 divided by 2: 15 full patterns, and 0 left over.
Careful!
Nothing left over means we end at the end of a pattern: the same place as k = 2.
So 4 to the 30 is like k = 2: the last one of the pattern.
So 4³⁰ mod 5 is 1.
4 Check
A computer can work out all 19 digits: 115292, and so on, 6976.
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 30 lands.
Last: check.