Worked examples
The question
Question: find 3¹⁰⁰ mod 5.
3100 mod 5
3 to the power 100 has 48 digits.
Too big to work out by hand.
3100 has 48 digits!
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.
only the remainder matters
3 to the 1 is 3.
3
3
Then 3 times 3 is 9.
3 × 3 = 9
9 mod 5 is 4.
And so on.
4
4 × 3 = 12
2
2 × 3 = 6
1
1 × 3 = 3
3
2 Find the pattern
At k = 5 we are back to 3.
From here everything repeats.
So the pattern 3, 4, 2, 1 repeats every 4 powers.
repeats every 4: 3, 4, 2, 1, 3, 4, 2, 1, ...
3 Where 100 lands
100 divided by 4: 25 full patterns, and 0 left over.
100 = 4 × 25 + 0
Careful!
Nothing left over means we end at the end of a pattern: the same place as k = 4.
Careful: not k = 0 ✗
So 3 to the 100 is like k = 4: the last one of the pattern.
So 3¹⁰⁰ mod 5 is 1.
3100 mod 5 = 1
4 Check
A computer can work out all 48 digits: 515377, and so on, 2001.
computer: 3100 = 515377...2001
Divided by 5, it leaves 1, the same as our pattern.
Right!
÷ 5: remainder 1
Let's look back.
First: small powers first.
Then: find the pattern.
Then: where 100 lands.
Last: check.
▶ Watch it solved
The question
Question: find 2⁵⁰ mod 7.
250 mod 7
2 to the power 50 has 16 digits.
Too big to work out by hand.
250 has 16 digits!
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.
only the remainder matters
2 to the 1 is 2.
2
2
Then 2 times 2 is 4.
2 × 2 = 4
4 mod 7 is 4.
And so on.
4
4 × 2 = 8
1
1 × 2 = 2
2
2 Find the pattern
At k = 4 we are back to 2.
From here everything repeats.
So the pattern 2, 4, 1 repeats every 3 powers.
repeats every 3: 2, 4, 1, 2, 4, 1, ...
3 Where 50 lands
50 divided by 3: 16 full patterns, and 2 left over.
50 = 3 × 16 + 2
Careful!
The pattern is all we need.
The full number is far too big.
Careful: never work out 2⁵⁰ itself
So 2 to the 50 is like k = 2.
So 2⁵⁰ mod 7 is 4.
250 mod 7 = 4
4 Check
A computer can work out all 16 digits: 112589, and so on, 2624.
computer: 250 = 112589...2624
Divided by 7, it leaves 4, the same as our pattern.
Right!
÷ 7: remainder 4
Let's look back.
First: small powers first.
Then: find the pattern.
Then: where 50 lands.
Last: check.
▶ Watch it solved
The question
Question: find the last digit of 8¹²³.
last digit of 8123
8 to the power 123 has 112 digits.
Too big to work out by hand.
8123 has 112 digits!
The last digit is the remainder after dividing by 10.
So we work mod 10.
last digit = the remainder after ÷ 10
1 Small powers first
Let's make a table of small powers.
Each one is the one before times 8.
We only keep the remainder: the big part never matters.
only the remainder matters
8 to the 1 is 8.
8
8
Then 8 times 8 is 64.
8 × 8 = 64
64 mod 10 is 4.
And so on.
4
4 × 8 = 32
2
2 × 8 = 16
6
6 × 8 = 48
8
2 Find the pattern
At k = 5 we are back to 8.
From here everything repeats.
So the pattern 8, 4, 2, 6 repeats every 4 powers.
repeats every 4: 8, 4, 2, 6, 8, 4, 2, 6, ...
3 Where 123 lands
123 divided by 4: 30 full patterns, and 3 left over.
123 = 4 × 30 + 3
Careful!
The pattern is all we need.
The full number is far too big.
Careful: never work out 8¹²³ itself
So 8 to the 123 is like k = 3.
So the last digit of 8¹²³ is 2.
last digit of 8123 = 2
4 Check
A computer can work out all 112 digits: 120245, and so on, 7712.
computer: 8123 = 120245...7712
It ends in 2, the same as our pattern.
Right!
last digit: 2
Let's look back.
First: small powers first.
Then: find the pattern.
Then: where 123 lands.
Last: check.
Answer last digit of 8123 = 2
▶ Watch it solved
