The user-friendly version of this content is available here.
The following content is copyright (c) 2009-2013 by Goods of the Mind, LLC.
This essential trains for: AMC-8, AMC-10, AMC-12, AIME, Math Kangaroo 7-8, Math Kangaroo 9-10.
Modular arithmetic is the arithmetic of remainders. It helps us compute remainders from integer divisions much more rapidly than the direct use of the division algorithm. In many cases, it is possible to make progress in a problem by using modular arithmetic when there is not enough information to divide directly.
Notation: The "mod" notation replaces the division theorem statement and ignores the quotient. The division:
is denoted by:
where the quotient is ignored, only the divisor and the remainder are important.
Since 2 is smaller than both 3 and 5, this division can be construed as being either a division by 3 or a division by 5:
Addition property: If two numbers have certain remainders upon division by a given divisor, the sum of their remainders will be the remainder from dividing their sum by the same divisor.
To prove this, let's first apply the division theorem. Let the two numbers be N and M, and the divisor be d:
We are not interested in the quotients a and b but only in the remainders. Let's first add the equations:
and "massage" this equation to make it look like the integer division theorem again:
This looks like a division by the same divisor d. The quotient appears to be a+b but we are not interested in it. The remainder appears to be n+m which is, as the rule states, the sum of the two remainders under the same division.
Using modular notation:
However, we must remember that, according to the integer division theorem, the remainder must be strictly less than the divisor. Or, because we are adding two remainders, it is not guaranteed that the result n+m will be less than d. To find the true remainder, we might have to divide again. This would increase the quotient, but we are ignoring the quotient anyways.
The true remainder would be r':
What is the use of the addition property? Even though we may have to perform one more division at the end, the numbers involved in the division are going to be much smaller. The advantage of the method is that of keeping your numbers small. In problem solving, keeping your numbers small is very important.
Multiplication property: If two numbers have certain remainders under division by a given divisor, the product of their remainders will be the remainder from dividing their product by the same divisor.
Once again, to prove this we first apply the division theorem:
Again, we can "massage" this expression to make it look like the integer division theorem:
We see that, for the same divisor d, we obtain a complicated quotient — which we are not interested in — and the remainder mn.
Using modular notation:
The same observation applies, that this remainder may be larger than the divisor d, and is therefore not an actual remainder. We may have to perform another division by d.
Integer power property: If a positive integer N has remainder n when divided by a positive integer d, then N raised to a positive integer power x has the same remainder when divided by d as n raised to the power x has.
The integer power property is easily proven from the multiplication property. In the multiplication property, make N=M:
We notice that the remainder of the power is the power of the remainder, up to the same observation that it may be larger than the divisor and require more division.
Generalizing to repeated multiplication:
Applications: How do we use the integer power property in problem solving? It enables us to compute remainders of very large powers.
Note that, should some remainder be 0, 1 or -1, any power of these bases is easily computed. Therefore, we must aim to obtain one of these remainders if possible. In particular, many problems are based on the remainder -1, since a "direct approach" would start with the largest possible remainder instead, making the problem slightly harder.
Example: Consider the problem of solving for the remainder x:
We first ignore the exponent and perform the division:
it is obvious that any power of that base will have the same remainder, in particular the power specified in the example:
Example: Again, the problem is to solve for the remainder x:
we notice that, by squaring the number we obtain one of the 'magic' remainders:
Therefore, further even powers will keep this remainder unchanged:
To get the next power, multiply again by the equivalence for the first power of the base:
As mentioned above, using negative remainders is a useful problem-solving technique for rapidly obtaining a result.
The meaning of a negative remainder is based on the fact that the quotient is ignored by modular arithmetic. Therefore, we can reach any number either by adding something to the multiple that is smaller than it or by subtracting something from the next larger multiple. Look at the number line for an example, using division by 6:
Consider the problem of finding the remainder when we divide
by 13. We aim to use the rule for integer powers. Therefore, first look at:
which means that 168 is in the class of remainders 12 with respect to division by 13:
If we were to use the integer power rule on this congruence, we would have to take successive powers of 12 modulo 13. This is not difficult, as a pattern quickly emerges (try it!). Nevertheless, it's simpler to go by negative remainders:
The remainder is 12.