Proving Congruence For Fun
Background
I want to understand the math behind asymmetric cryptography.^{1} This field relies heavily on Modular Arithmetic.^{2} I bought an undergraduate math textbook for selfstudy. 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\geq1\) be an integer.
(a) If \(a_1\equiv a_2 \pmod{m}\) and \(b_1\equiv b_2 \pmod{m}\), then
\(a_1\cdot b_1\equiv a_2\cdot b_2 \pmod{m}\)
Proof
The definition of congruence: m divides \(a_1a_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+km)\times(b_2+jm)$$
Use the FOIL method for multiplying binomials.
$$a_1\times b_1=a_2\times b_2+a_2\times jm+b_2\times km+km\times jm$$
We now consider each term in this equation \(\pmod{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 \pmod{m}\) is zero. This leaves the final equation as: $$a_1\times b_1=a_2\times b_2 \pmod{m}$$
References

Wikipedia article references PublicKey Cryptography which is directly linked from asymmetric cryptography. ↩︎

Wikipedia information on Modular Arithmetic ↩︎