Modular Arithmetic

Recall: for integers a and b with b > 0, we define q := a div b and r := a mod b so that r is nonnegative has the same sign as `a` .

To find what day of the week it will be in the future, you can do arithmetic modulo 7 31 365 .

Depending on how your clock works, the hours might behave according to arithmetic modulo 12 or 24 12 or 60 24 or 168 .

Congruence

We say that a is congruent to b modulo m, or a ≡ b (mod m), if m | b-a. Equivalently, this means that there exists an integer k such that a = bm + k a = km + b m = ak + b .

True or false: if a ≡ b (mod m) then b ≡ a (mod m). True False

Using congruence to simplify computations

Here are two useful facts about congruence:

• If a ≡ b (mod m) and c ≡ d (mod m), then a+c ≡ b+d (mod m).
• If a ≡ b (mod m) and c ≡ d (mod m), then ac ≡ bd (mod m).

One consequence is that we can compute large sums and products modulo m by computing the remainders modulo m before doing any arithmetic.

We can use this theorem to solve modular arithmetic problems with large inputs by reducing modulo m first, so that we don't have to deal with large intermediate quantities.

Try it yourself:

Note that the above theorem does not hold for exponentiation. Furthermore, we cannot always "cancel out" multiplicative factors modulo m.