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:

equation

is denoted by:

equation

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:

equation

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:

equation

equation

We are not interested in the quotients a and b but only in the remainders. Let's first add the equations:

equation

and "massage" this equation to make it look like the integer division theorem again:

equation

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:

equation

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':

equation

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:

equation

equation

equation

Again, we can "massage" this expression to make it look like the integer division theorem:

equation

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:

equation

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:

equation

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:

equation

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:

equation

We first ignore the exponent and perform the division:

equation

Since:

equation

it is obvious that any power of that base will have the same remainder, in particular the power specified in the example:

equation

equation

Example: Again, the problem is to solve for the remainder x:

equation

Since

equation

we notice that, by squaring the number we obtain one of the 'magic' remainders:

equation

Therefore, further even powers will keep this remainder unchanged:

equation

To get the next power, multiply again by the equivalence for the first power of the base:

equation

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:

figure

Consider the problem of finding the remainder when we divide

equation

by 13. We aim to use the rule for integer powers. Therefore, first look at:

equation

which means that 168 is in the class of remainders 12 with respect to division by 13:

equation

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:

equation

equation

equation

equation

The remainder is 12.