This text should not be just read: think of examples, of the reasons between the stated statements. Try to prove as much of the written as possible. A lot of small proofs are omitted here for readability and relative conciseness.
Consider the set of remainders when dividing by a fixed number . Due to the properties of moduli arithmetic (see congruence properties), this set can be endowed with addition and multiplication inherited from integer numbers. Then this set together with the operations is denoted .
The operations work in the following way: to add two remainders, take any two integer numbers with this remainder, add them as integers and take the remainder of the sum. One proceeds similarly for multiplication: to multiply two remainders, one takes any two integer numbers with these remainders, multiplies them as integers and takes the remainder of the product. The operations are well-defined, i.e., the result does not depend on the choice of the numbers with the given remainders: without this one would not know what value to associate to the sum or product of two remainders.
Equality in is synonymous to congruence modulo . In other words, two remainders are equal if their integer representatives are congruent modulo . We will usually use congruences instead of operations inside to avoid ambiguity (are we working with integers or remainders?). This parallel is here to emphasize why do we think about congruence as something similar to equality: it is a “weaker equality”, one that only compares the remainder of the integer number.
In integers, equality has the following properties:
Reflexivity: for any .
Symmetry: if , then .
Transitivity: if and , then .
Congruence of integers modulo satisfies the same properties: if , then and if and , then .
In integers (and reals) we are used to do cancellations in equalities: if , then . However, the result that actually holds directly without any additional assumptions is the converse one: if , then as we are performing the same operation with equal numbers. The cancellation property is a consequence of invertibility of addition: if , then , so . This argument directly translates to congruences.
For multiplication, the situation is different: if , then for integer if is not zero. But multiplication is not invertible in integers (there does not exist a number such that for all )! So why does cancellation still work? The easiest way to explain it is the following: consider the map for fixed . This map is injective (if , then ), so it is invertible in the sense that it has a left inverse: . This means that if , then for any . Alternatively, one can first extend the set of integers to the set of rationals and then use the invertibility of multiplication in rationals.
In remainders, the map is not injective, so the argument above does not work. Invertibility of multiplication also does not hold.
To recap, the following is true in integers:
Lemma
If , and , then .
So what result holds in remainders? It turns out that you can cancel coefficients that are relatively prime to your modulo:
Lemma
If , and , then .
Example
Let . Then , but .
The proof of this result is a direct consequence of the invertibility of multiplication in : if is invertible, then one can cancel it. If is not invertible, then one cannot cancel it (why?). (See Invertibility of elements in congruences for more details.)