Journey into cryptography

# Modular arithmetic

## Equivalent Statements

Before proceeding it’s important to remember the following statements are equivalent

• A \equiv B\ (\text{mod }C)

• A \text{ mod } C = B \text{ mod }C

• C \ |\ (A - B) The | symbol means divides, or is a factor of)

• A = B + K \cdot C (where K is some integer)

This lets us move back and forth between different forms of expressing the same idea.

For example the following are equivalent:

• 13 \equiv 23\ (\text{mod }5)

• 13 \text{ mod } 5 \equiv 23 \text{ mod }5

• 5 \ |\ (13 - 23), (5 \ |\ -10, which is true since \bf{5 \times -2 = -10} )

• 13 = 23 + K \cdot 5. We can satisfy this with \bf{K = -2}: 13 = 23 + (-2) \times 5

## Congruence Modulo is an Equivalence Relation

Convince yourself that the slices used in the previous example have the following properties:

• Every pair of values in a slice are related to each other

• We will never find a value in more than one slice (slices are mutually disjoint)

• If we combine all the slices together they would form a pie containing all of the values

A pie with slices that have these properties has an equivalence relation.
An equivalence relation defines how we can cut up our pie (how we partition our set of values) into slices (equivalence classes).

In general, equivalence relations must have these properties:

• The pie: A collection of all the values we are interested in

• A slice of pie: An equivalence class

• How we cut the pie into slices: equivalence relation

Specifically, for our previous example:

• The pie: The collection of all integers

• A slice of pie labelled B: Equivalence class where all the values \text{mod } C = B

• How we cut the pie into slices: Using the congruence modulo C relation, \equiv (\text{mod } C)

This is why we say that Congruence modulo C is an equivalence relation. It partitions the integers into C different equivalence classes.

## Why do we care that congruence modulo C is an equivalence relation ?

Knowing that congruence modulo C is an equivalence relation lets us know about some properties that it must have.
Equivalence relations are relations that have the following properties:

• They are reflexive: A is related to A

• They are symmetric: if A is related to B, then B is related to A

• They are transitive: if A is related to B and B is related to C then A is related to C

Since congruence modulo is an equivalence relation for (mod C). This means:

• A \equiv A \ (\text{mod } C)

• if A \equiv B \ (\text{mod }C) then B \equiv A \ (\text{mod }C)

• if A \equiv \bf{B} \ (\text{mod } C)  and \bf{B} \equiv D \ (\text{mod } C) then \bf{A \equiv D} \ (\text{mod } C)

## Example

Let's apply these properties to a concrete example using \text{mod }5:

• 3 \equiv 3\ \text{ mod } 5 (reflexive property)

• if 3 \equiv 8\ (\text{mod }5) then 8 \equiv 3\ (\text{mod }5) (symmetric property)

• if 3 \equiv 8\ (\text{mod }5) and if 8 \equiv 18\ (\text{mod }5) then 3 \equiv 18\ \text{ mod }5 (transitive property)