# Modular Arithmetic/Modular Arithmetic

 Modular Arithmetic ← What is a Modulus? Modular Arithmetic The Pigeonhole Principle →

## Introduction

Previously we gave examples of some modular congruences using the analogy of clock arithmetic – 27 hours from now will be the same time as 3 hours from now. In English we would say 27 is congruent to 3 modulo 24. Expressed mathematically, we would write:

${\displaystyle 27\equiv 3{\pmod {24}}}$.

Note the congruent sign has three horizontal lines and not two like an equals sign.

In general, for any integers ${\displaystyle a,b}$ and any integer ${\displaystyle c\neq 0}$ , the congruence ${\displaystyle a\equiv b{\pmod {c}}}$ is equivalent to the following:

1. ${\displaystyle {\frac {a-b}{c}}}$ is an integer
2. ${\displaystyle c{\bigl |}(a-b)}$ (${\displaystyle c}$ divides ${\displaystyle a}$ minus ${\displaystyle b}$)
3. there exists some integer ${\displaystyle x}$ such that ${\displaystyle cx+b=a}$

Using our previous example ${\displaystyle 27\equiv 3{\pmod {24}}}$ , we see that:

1. ${\displaystyle {\frac {27-3}{24}}=1}$
2. ${\displaystyle 24{\bigl |}(27-3)}$
3. ${\displaystyle 24\cdot 1+3=27}$

Now that we have a definition of modular congruence, we can go on to state some basic properties of the congruence relation (${\displaystyle \equiv }$) itself. The congruence relation is an equivalence relation, which means that the congruence relation is reflexive, symmetric, and transitive. Since the equality relation (${\displaystyle =}$) is also an equivalence relation we can demonstrate these three properties easily; for any integers ${\displaystyle a,b,c}$ :

1. Reflexive: ${\displaystyle a=a}$
2. Symmetric: if ${\displaystyle a=b}$ then ${\displaystyle b=a}$
3. Transitive: if ${\displaystyle a=b}$ and ${\displaystyle b=c}$ then ${\displaystyle a=c}$

Analogously, for the congruence relation (${\displaystyle \equiv }$) satisfies these three properties; for any integers ${\displaystyle a,b,d}$ and any integer ${\displaystyle c\neq 0}$ :

1. Reflexive: ${\displaystyle a\equiv a{\pmod {c}}}$
2. Symmetric: if ${\displaystyle a\equiv b{\pmod {c}}}$ then ${\displaystyle b\equiv a{\pmod {c}}}$
3. Transitive: if ${\displaystyle a\equiv b{\pmod {c}}}$ and ${\displaystyle b\equiv d{\pmod {c}}}$ then ${\displaystyle a\equiv d{\pmod {c}}}$
 Exercises: Equivalence Relations Prove that the congruence relation (${\displaystyle \equiv }$) is reflexive, symmetric, and transitive. Which of the following relations are congruence relations: Less than (${\displaystyle <}$) Greater than (${\displaystyle >}$) Less than or equal to (${\displaystyle \leq }$) Greater than or equal to (${\displaystyle \geq }$) Not equal to (${\displaystyle \neq }$)

We took what appears to be a detour through equivalence relations, because those three properties allow us to define addition, subtraction, and multiplication for congruences. Addition, subtraction, and multiplication work exactly the same way as they do with integers with the only constraint being that addition, subtraction, and multiplication is only allowed when the congruences have the same moduli. Mathematically, suppose we have some ${\displaystyle a_{1}\equiv b_{1}{\pmod {c}}}$ and ${\displaystyle a_{2}\equiv b_{2}{\pmod {c}}}$ then:

1. ${\displaystyle a_{1}\pm a_{2}\equiv b_{1}\pm b_{2}{\pmod {c}}}$ (Addition and Subtraction)
2. ${\displaystyle a_{1}\cdot a_{2}\equiv b_{1}\cdot b_{2}{\pmod {c}}}$ (Multiplication)

For example, since 23 ≡ 3 (mod 4) and 6 ≡ 2 (mod 4) the following are true:

1. (23 + 6) ≡ (2 + 3) (mod 4) = 29 ≡ 5 (mod 4) = 29 ≡ 1 (mod 4) (Addition)
2. (23 - 6) ≡ (2 - 3) (mod 4) = 17 ≡ -1 (mod 4) = 17 ≡ 3 (mod 4) (Subtraction)
3. (23 * 6) ≡ (2 * 3) (mod 4) = 138 ≡ 6 (mod 4) = 138 ≡ 2 (mod 4) (Multiplication)

Again, as long as we have the same moduli between two congruences, we can add, subtract, and multiply them together.

 Exercises: Equivalence Relations Using the definition of congruences and the fact that it is an equivalence relationship, prove that addition, subtraction, and multiplication are valid for congruences with the same moduli.

## Division

Just as we cannot divide by zero in normal arithmetic, division for modular congruences is only allowed under certain circumstances. For example, just because ${\displaystyle 14\equiv 4{\pmod {10}}}$ we cannot divide both sides by two because ${\displaystyle 7\not \equiv 2{\pmod {10}}}$ . Mathematically, if ${\displaystyle bd_{1}\equiv bd_{2}{\pmod {c}}}$ and if ${\displaystyle \gcd(b,c)=1}$ then ${\displaystyle d_{1}\equiv d_{2}{\pmod {c}}}$ .

${\displaystyle \gcd(b,c)}$ means the greatest common divisor for ${\displaystyle b,c}$ – the greatest number that divides both ${\displaystyle b}$ and ${\displaystyle c}$ . When the greatest common divisor of two numbers is 1, that means there are no other common divisors (i.e. they are relatively prime). Our example of ${\displaystyle 14\equiv 4{\pmod {10}}}$ fails to divide by 2, because both 2 and 10 are divisible by 2. Again, we can only divide provided that there are no common divisors between the number we are trying to divide by and the modulus. Note that if the modulus is a prime number, then division is defined for all divisors.