Congruence

#matematik-discmath

Definition: Congruent, modulo

Let and . We say that is congruent to modulo and write if is Divisible Divisible by .

Note that congruence clearly is an Equivalence relation Equivalence relation since if and then .

Theorem

Let and such that and . Then and .

Proof:
We know and . This gives and

Notation

We let denote the equivalence class of with respect to congruence modulo .

For example, . Also notice that since any can be expressed as for some , the unique equivalence classes are .

Definition: Integers modulo

is the set of distinct equivalence classes under the relation of congruence modulo in , so We also define the following operations:

From Theorem Theorem, it follows easily that these operations are well-defined. Of course, since we transfer the operations to integer operations, the properties of these integer operations, like associativity, commutativity and additive inverses, apply here too. However, for example the rule that if then , does not apply here: we only get that meaning , which of course does not necessarily imply that .

Definition: Invertibility

An element is invertible if there exists a such that . In this case, is called the multiplicative inverse or just inverse of .

From the commutativity of multiplication we see immediately that is the inverse of , so for every invertible .

Theorem

is invertible if and only if and are coprime in .

Proof:
: We have for some , meaning . Any common divisor of and must divide , so .
: By Bézout's identity Bézout's identity there are such that , meaning , so in equivalence class terms, so .

We thus see that if is prime, then every element of except is invertible. Also, the number of invertible elements in is .

Theorem

If is invertible, then .

Proof:
We let , and see that is invariant under multiplication with elements in ; we define , and then see that for any , , so, , meaning for every . Let be the invertible elements of , where . Since is invertible and , we see that meaning since is invertible.

Corollary: Euler's theorem, Fermat's little theorem

From the previous theorem it immediately follows that if , then , which is Euler's theorem. It also follows that if is prime, then , which is Fermat's little theorem.