Proving Congruence For Fun

Background

I want to understand the math behind asymmetric cryptography.¹ This field relies heavily on Modular Arithmetic.² I bought an undergraduate math textbook for self-study. This article is a record of a proof exercise in the book. It is also a good exercise in writing math equations using LaTeX.

NOTE: I asked ChatGPT to confirm the proof. No grades are being assigned here, the point is to learn.

Problem

Let $m \geq 1$ be an integer.

(a) If $a_{1} \equiv a_{2} (\mod m)$ and $b_{1} \equiv b_{2} (\mod m)$ , then

$a_{1} \cdot b_{1} \equiv a_{2} \cdot b_{2} (\mod m)$

Proof

The definition of congruence: m divides $a_{1} - a_{2}$ In an equation this can be written as: $a_{1} = a_{2} + k \cdot m$ and $b_{1} = b_{2} + j \cdot m$

If we multiply the right and left sides of these equations: $a_{1} \times b_{1} = (a_{2} + k m) \times (b_{2} + j m)$

Use the FOIL method for multiplying binomials.

$a_{1} \times b_{1} = a_{2} \times b_{2} + a_{2} \times j m + b_{2} \times k m + k m \times j m$

We now consider each term in this equation $(\mod m)$ All of the terms with that are multiples of m will drop out of the equation since for any integer x: $x \times m (\mod m)$ is zero. This leaves the final equation as: $a_{1} \times b_{1} = a_{2} \times b_{2} (\mod m)$

References

Wikipedia article references Public-Key Cryptography which is directly linked from asymmetric cryptography. ↩︎
Wikipedia information on Modular Arithmetic ↩︎