Basic Modular Arithmetic Modulo N

Modulo Arithmetic : The basic properties

Previous Part

In the last part of the article, we've look at what modulo arithmetic is. In this part, we'll look at some basic properties.

There, we have four of the basic properties. Note that $\frac{a}{c} \equiv \frac{b}{c} \pmod{m}$ does not neccearily follow. For example, $6 \equiv 4 \pmod{2}$, but $3 = \frac{6}{2} \not\equiv \frac{4}{2} = 2\pmod{2}$.

So, in what scenario can we divide like that?

Indeed, an example is if $10 \equiv 20 \pmod{5}$, then $5 \equiv 10 \pmod{5}$. We leave the proof of all these properties to the reader.

In addition,

That's all for the basic properties of modulo arithmetic.

Next part

Performing operations in Modular Arithmetic

Addition and Subtraction

**A1: ** Given that $a\equiv b \pmod n$, then $a+c\equiv b+c \pmod n$

**Proof: ** $(a+c)-(b+c)=a-b=kn$

A2 Given that $a\equiv b \pmod n$ and $c\equiv d \pmod n$, then $a+c\equiv b+d \pmod n$

Proof $a\equiv b \pmod n$ implies $a-b=kn$. $c\equiv d \pmod n$ implies $c-d=pn$

Hence:

$$(a-b)+(c-d)=kn+pn$$ $$(a+c)-(b+d)=kn+pn$$ $$a+c\equiv b+d \pmod n$$

**Note: ** In the two properties of addition in modular arithmetic above, $a$, $b$, $c$, and $d$ doesn't nessesarily have to be positive numbers, they can be negative as well, but they must be integers. Hence, these properties can be extended into subtraction.

Multiplication and Exponentation

**M1: ** Given that $a\equiv b \pmod n$, then $ac\equiv bc \pmod n$

**Proof: ** $a\equiv b \pmod n$ implies $a-b=kn$, multiplying both sides by $c$ acheives the desired result.

**M2: ** Given that $a\equiv b \pmod n$ and $c\equiv :d \pmod n$, then $ac\equiv bd \pmod n$

**Proof: **

$$\begin{aligned}a\equiv b \pmod n &\implies ac\equiv bc \pmod n \\c\equiv d \pmod n &\implies bc\equiv bd \pmod n \\ac \equiv bc \equiv bd \pmod n &\implies \boxed{ac\equiv bd \pmod n}\end{aligned}$$

**M3: ** Given that $a\equiv b \pmod n$, then $a^c\equiv b^c \pmod n$

**Proof: ** This is proven thorugh repeatedly applying property M2.

Multiplication modulo C

$(A \times B)$ mod$(C)$ $=$ $(A$ mod$(C)) \times (B$ mod$(C))$ mod$(C)$

This are easy to prove simply by considering $A$ as the number $C \cdot q_a + r_a$, and $B$ as the number $C \cdot q_b + r_b$, where $0 \le r_a, r_b < C$ and $q_a, q_b$ are integers. This is possible to do because of the Quotient Remainder Theorem.

Substituting for $A$ and $B$ in the equation above, we get $((C \cdot q_a + r_a )(C \cdot q_b + r_b))$ mod$(C) = (r_a \cdot r_b )$ mod$(C)$.

Then, if we multiply out the left hand side, we get $(C \cdot (C \cdot q_a \cdot q_b + q_a \cdot r_b + q_b \cdot r_a) + r_a \cdot r_b )$ mod$(C) = (r_a \cdot r_b )$ mod$(C)$.

But, because $C$ mod$(C) = 0$, the left hand side simplifies to $(r_a \cdot r_b)$ mod$(C)$, which equals the right side and completes our proof. $\square$

Addition modulo C

$(A + B)$ mod$(C)$ $=$ $(A$ mod$(C)) + (B$ mod$(C))$ mod$(C)$

This can be proved in a similar way as the one above. If we take $A$ as the number $C \cdot q_a + r_a$, and $B$ as the number $C \cdot q_b + r_b$, we can prove this relationship quite easily. I will leave this proof as an exercise for the reader.