Modular Arithmetic/Modular Arithmetic

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:

$27\equiv 3(\mathrm{mod}24)$.

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

In general, for any integers $a,b$ and any integer $c\ne 0$ , the congruence $a\equiv b(\mathrm{mod}c)$ is equivalent to the following:

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

Using our previous example $27\equiv 3(\mathrm{mod}24)$ , we see that:

1. $\frac{27-3}{24}=1$
2. $24|(27-3)$
3. $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 ($\equiv$) itself. The congruence relation is an equivalence relation, which means that the congruence relation is reflexive, symmetric, and transitive. Since the equality relation ($=$) is also an equivalence relation we can demonstrate these three properties easily; for any integers $a,b,c$ :

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

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

1. Reflexive: $a\equiv a(\mathrm{mod}c)$
2. Symmetric: if $a\equiv b(\mathrm{mod}c)$ then $b\equiv a(\mathrm{mod}c)$
3. Transitive: if $a\equiv b(\mathrm{mod}c)$ and $b\equiv d(\mathrm{mod}c)$ then $a\equiv d(\mathrm{mod}c)$

Prove that the congruence relation ($\equiv$) is reflexive, symmetric, and transitive.

Which of the following relations are congruence relations:

• Less than ($<$)
• Greater than ($>$)
• Less than or equal to ($\le$)
• Greater than or equal to ($\ge$)
• Not equal to ($\ne$)

Addition, Subtraction, Multiplication

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 $a_1\equiv b_1(\mathrm{mod}c)$ and $a_2\equiv b_2(\mathrm{mod}c)$ then:

1. $a_1\pm a_2\equiv b_1\pm b_2(\mathrm{mod}c)$ (Addition and Subtraction)
2. $a_1\cdot a_2\equiv b_1\cdot b_2(\mathrm{mod}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.

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 $14\equiv 4(\mathrm{mod}10)$ we cannot divide both sides by two because $7\equiv ̸2(\mathrm{mod}10)$ . Mathematically, if $b{d}_1\equiv b{d}_2(\mathrm{mod}c)$ and if $\gcd (b,c)=1$ then $d_1\equiv d_2(\mathrm{mod}c)$ .

$\gcd (b,c)$ means the greatest common divisor for $b,c$ – the greatest number that divides both $b$ and $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 $14\equiv 4(\mathrm{mod}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. Template:BookCat