From "Cut The Knot" — A Nice Use of the Pigeonhole Principle
Monday 14 September 2026 at 17:23
Visible to anyone in the world
Edited by Richard Walker, Monday 14 September 2026 at 18:27
The Pigeonhole Principle says, of course, that if there are more pigeons than pigeonholes then we must be able to find a pigeonhole with more than one occupant.
The Cut The Problem ask for a proof (using the Pigeonhole Principle) that there is a power of whose last three digits are , which sounds quite surprising.
But let's imagine we have pigeonholes numbered . Calculate distinct power of , divide each by and find the remainder, then put that power in the pigeonhole with the same number as the remainder.
There is one more 'pigeons' than pigeonholes, so there must be a pigeonhole with two occupants, that it, two powers that leave the same remainder on division by .
Suppose these are and , being the smaller. Because they leave the same remainder when divided by , must be a multiple of .
can't divide a power of , so it must divide . This means when worked out ends in three zeros , which in turn means ends in .
We can run a computer search quite easily and we find that in fact
fits the bill.
This result can be generalised of course and we can prove that for example there must a power of that ends in a trillion zeros followed by , although given that even the zeros would take up nearly GB the browser is too small to display it.
From "Cut The Knot" — A Nice Use of the Pigeonhole Principle
The Pigeonhole Principle says, of course, that if there are more pigeons than pigeonholes then we must be able to find a pigeonhole with more than one occupant.
The Cut The Problem ask for a proof (using the Pigeonhole Principle) that there is a power of whose last three digits are , which sounds quite surprising.
But let's imagine we have pigeonholes numbered . Calculate distinct power of , divide each by and find the remainder, then put that power in the pigeonhole with the same number as the remainder.
There is one more 'pigeons' than pigeonholes, so there must be a pigeonhole with two occupants, that it, two powers that leave the same remainder on division by .
Suppose these are and , being the smaller. Because they leave the same remainder when divided by , must be a multiple of .
can't divide a power of , so it must divide . This means when worked out ends in three zeros , which in turn means ends in .
We can run a computer search quite easily and we find that in fact
fits the bill.
This result can be generalised of course and we can prove that for example there must a power of that ends in a trillion zeros followed by , although given that even the zeros would take up nearly GB the browser is too small to display it.