Congruence

Carl Friedrich Gauss, in his landmark work Disquisitiones Arithmeticæ, introduced congruence notation.

Definition

Let be a fixed positive integer. For integers and , we say that is congruent to modulo , and write

when . For integers and such that , we write . We refer to as congruence, and as its modulus.

Lemma

(See If and Only If)

Remark

Note that the has NO connection to logical equivalency

Example

Elementary Properties of Congruence

Consider be a fixed integer

Congruence is an Equivalence Relation (CER)

See Equivalence Relation

Proposition

For all integers , , and , we have

(see implication)
(see logical and)

Proof

Let be an arbitrary integer
Since and , the definition of congruence gives
Let and be arbitrary integers, and assume that
We have , so for some integer , .
Now, , so we have , and the definition of congruence gives
Let , , and be arbitrary integers, and assume that and
We have and .
By DIC, we have , so , and the definition of congruence gives

Congruence Add and Multiply (CAM)

Proposition

For all positive integers , for all integers , and , if for all , then

Congruence Power (CP)

Proposition

For all positive integers and integers and , if , then

Congruence Divide (CD)

Proposition

For all integers , , and , if and , then

(See GCD)

Proof

Let , , and be arbitrary integers, and assume that , and .
Since , we obtain by the definition of congruence, so .
Since , we can apply Coprimeness and Divisibility, which gives .
By definition of congruence, we conclude that