One of the most important tools in maths is the Pigeonhole Principle.
You may have already met it before, but if not, let’s recap it quickly.
Simply put: the Pigeonhole Principle states that if you have \(n\) pigeons (or objects) that you want to
place into a number of pigeonholes (or containers) that is strictly
smaller than \(n\), e.g: \(10\) pigeons but only \(9\) pigeonholes, then there will be a
pigeonhole with at least two pigeons. Today we will see how this
principle can be used to solve problems about numbers and their
divisibility properties.
Before we get started, we need to recap a very important concept: if we
have two numbers, say \(a\) and \(b\), we can divide \(a\) by \(b\), and we will obtain a quotient
\(q\) and a remainder \(r\), and write \[a=q\times b + r\] for example: if we
divide \(9\) by \(4\), we can write \(9=2\times 4 + 1\), i.e: the quotient will
be \(2\) and the remainder will be
\(1\).