Modular arithmetic (MOD) is a crucial topic within number theory and a required course for math majors. Moreover, almost all math competitions include MOD-related problems, often more than one. Consequently, MOD-related brain teasers are favored by many high-tech companies.
While MOD can be complex, the required knowledge for solving brain teasers is straightforward and understandable by everyone: remainders can be added and subtracted just like regular numbers.
For example, the units digit of an integer is essentially the remainder of that integer divided by $10$. To apply the aforementioned principle, we find that the units digit of the sum of two numbers is the same as the units digit of the sum of their units digits. Consider the example where the units digit of the sum of $26 + 17$ is the same as the units digit of $6 + 7$, where $6$ and $7$ are the units digits of $26$ and $17$, respectively. This principle also applies to subtraction. The units digit of $26 - 17$ is the same as $6 - 7$. However, in this case, we need to adjust the result from $-1$ to $9$, as the remainder cannot be negative.
Ensure you understand the above concept thoroughly before proceeding.
It is important to note that the divisor can be any integer, not necessarily $10$. For instance, if we use $2$ as the divisor, the conclusion translates to the following self-explanatory results:
To understand the connection between these rules and MOD, note that an odd number will have a remainder of $1$ when divided by $2$, and an even number will have a remainder of $0$. Thus, the above rules can be expressed using MOD equations.
Let's consider a practical example. In a problem involving different colors in a prison scenario, we can model each color as a different remainder. For instance, with two known colors, we label them as $0$ and $1$, implying a divisor of $2$. Similarly, with $100$ different colors, we model them as $0$ to $99$, implying a divisor of $100$. Following this, the brain teaser transforms into a straightforward MOD-related problem solvable by applying the principles discussed earlier.
$\textbf{Prisoners' Problem}$ One hundred prisoners will be lined up. Each one will be assigned either a red hat or a blue hat. No one can see the color of his or her own hat. However, each person is able to see the color of the hat worn by every person in front of him or her. That is, for example, the last person in line can see the colors of the hats on $99$ people in front of him or her; and the first person, who is at the front of the line, cannot see the color of any hat.Beginning with the last person in line, and then moving to the $99^{th}$ person, the $98^{th}$, etc., each will be asked to name the color of his or her own hat. He or she can only answer "red" or "blue". If the color is correctly named, the person lives; if not, the person is shot dead on the spot. Everyone in line is able to hear all the responses but not the gunshots.Before being lined up, the $100$ prisoners are allowed to discuss a strategy aiming to save as many of them as possible. How many people can be saved if they can agree on a good strategy? As a more challenging question, what if the hats can have $100$ known different colors instead of $2$?(3926)
The book Number Theory (MOD) is dedicated to this subject.