Modular arithmetic
a mod m denotes the remainder when a is divided by m.
Below, a, b, c, d are any integers and m is a positive integer.
We write a?b (mod m) (“a is congruent to b modulo m”) if
Note that a?b (mod m) iff a-b (and/or b-a) is a multiple of m.
- all even (or all odd) integers are congruent modulo 2
- all integers are congruent modulo 1
Theorem. If a ? b (mod m) and c ? d (mod m), then
a+c ? b+d (mod m) and ac ? bd (mod m).