Modular arithmetic

Definition

abmodm:kZ:ab=kma \equiv b \mod m :\Leftrightarrow \exists k \in \mathbb{Z} : a - b = k \cdot m

Basic properties

Addition and multiplication

abmodmcdmodm}{a+cb+dmodmacbdmodmacbdmodm\left.\begin{aligned} a &\equiv b \mod m \\ c &\equiv d \mod m \end{aligned}\right\rbrace \Rightarrow \left\lbrace\begin{aligned} a + c &\equiv b + d \mod m \\ a - c &\equiv b - d \mod m \\ a \cdot c &\equiv b \cdot d \mod m \end{aligned}\right.

Proof

By definition, ab=k1mcd=k2ma - b = k_1 \cdot m \\ c - d = k_2 \cdot m

Therefore:

(1): ab+cd=k1m+k2ma - b + c - d = k_1 m + k_2 m reordered gives (a+c)(b+d)=(k1+k2)m(a + c) - (b + d) = (k_1 + k_2)m.

(2): Follows trivially from (1)

(3): acbd=acbc+bcbd=c(ab)+b(cd)=ck1m+bk2m=(ck1+bk2)mac - bd = ac - bc + bc - bd = c(a - b) + b(c - d) = c k_1 m + b k_2 m = (c k_1 + b k_2)m

Powers

abmodmkN:akbkmodma \equiv b \mod m \Rightarrow \forall k \in \mathbb{N} : a^k \equiv b ^k \mod m

Proof

abmodmabmodm\begin{aligned} a \equiv b \mod m \\ a \equiv b \mod m \end{aligned}

implies a2b2modma^2 \equiv b^2 \mod m. For greater exponents the statement is true by induction.

Combination with different moduli

xamodn1n2{xamodn1xamodn2x \equiv a \mod n_1 n_2 \Rightarrow \left\lbrace\begin{aligned} x &\equiv a \mod n_1 \\ x &\equiv a \mod n_2 \end{aligned}\right.

If gcd(n1,n2)=1\gcd(n_1, n_2) = 1, then the converse also holds: xamodn1xamodn2}xamodn1n2\left.\begin{aligned} x &\equiv a \mod n_1 \\ x &\equiv a \mod n_2 \end{aligned}\right\rbrace \Rightarrow x \equiv a \mod n_1 n_2

General simultaneous congruences

It holds, that xa1modn1xa2modn2L}{a1a2modgcd(n1,n2)x1x2modlcm(n1,n2)x1,x2L\left.\begin{aligned} x &\equiv a_1 \mod n_1 \\ x &\equiv a_2 \mod n_2 \\ L &\neq \varnothing \end{aligned}\right\rbrace \Leftrightarrow \left\lbrace\begin{aligned} a_1 &\equiv a_2 \mod \gcd(n_1, n_2) \\ x_1 &\equiv x_2 \mod \lcm(n_1, n_2) \quad\forall x_1,x_2 \in L \end{aligned}\right.

where LL is the solution set.

Proof

(\Rightarrow): First, we prove that a1a_1 must be equivalent to a2a_2 modulo gcd(n1,n2)\gcd(n_1, n_2): {xa1modn1xa2modn2{xa10modn1xa20modn2{xa10modgcd(n1,n2)xa20modgcd(n1,n2)xa1x+a20modgcd(n1,n2)a2a10modgcd(n1,n2)a1a2modgcd(n1,n2)\begin{aligned} \left\lbrace\begin{aligned} x &\equiv a_1 \mod n_1 \\ x &\equiv a_2 \mod n_2 \end{aligned}\right. &\Rightarrow \left\lbrace\begin{aligned} x - a_1 &\equiv 0 \mod n_1 \\ x - a_2 &\equiv 0 \mod n_2 \end{aligned}\right. \\ &\Rightarrow \left\lbrace\begin{aligned} x - a_1 &\equiv 0 \mod \gcd(n_1, n_2) \\ x - a_2 &\equiv 0 \mod \gcd(n_1, n_2) \end{aligned}\right. \\ &\Rightarrow x - a_1 - x + a_2 \equiv 0 \mod \gcd(n_1, n_2) \\ &\Rightarrow a_2 - a_1 \equiv 0 \mod \gcd(n_1, n_2) \\ &\Rightarrow a_1 \equiv a_2 \mod \gcd(n_1, n_2) \end{aligned}

The set of solutions LL is defined modulo lcm(n1,n2)\lcm(n_1, n_2), because given x1,x2Lx_1, x_2 \in L \neq \varnothing it follows, that x1=a1+k1n1x1=a2+k2n2x2=a1+k3n1x2=a2+k4n2\begin{aligned} x_1 &= a_1 + k_1 \cdot n_1 \\ x_1 &= a_2 + k_2 \cdot n_2 \\ x_2 &= a_1 + k_3 \cdot n_1 \\ x_2 &= a_2 + k_4 \cdot n_2 \end{aligned}

where k1,k2,k3,k4Zk_1, k_2, k_3, k_4 \in \mathbb{Z}. By subtracting the third row from the first one and the fourth row from the second one we get: x1x2=a1+k1n1a1k3n1=(k1k3)n1x1x2=a2+k2n2a2k4n2=(k2k4)n2\begin{aligned} x_1 - x_2 &= a_1 + k_1\cdot n_1 - a_1 - k_3 \cdot n_1 = (k_1 - k_3) \cdot n_1 \\ x_1 - x_2 &= a_2 + k_2 \cdot n_2 - a_2 - k_4 \cdot n_2 = (k_2 - k_4) \cdot n_2 \end{aligned}

So x1x2x_1 - x_2 must be a multiple of both n1n_1 and n2n_2 and therefore: x1x20modlcm(n1,n2)x_1 - x_2 \equiv 0 \mod \lcm(n_1, n_2)

(\Leftarrow): By assumption, we know that for some kZk \in \mathbb{Z} a1a2=kgcd(n1,n2)a_1 - a_2 = k \cdot \gcd(n_1, n_2)

Also, as stated in the Bézout Lemma, we can write the greatest common divisor as a linear combination: gcd(n1,n2):=un1+vn2\gcd(n_1, n_2) := u \cdot n_1 + v \cdot n_2

By replacing gcd(n1,n2)\gcd(n_1, n_2) with the linear combination we get: a1a2=kun1+kvn2a_1 - a_2 = k \cdot u \cdot n_1 + k \cdot v \cdot n_2

Thus, a1kun1a1modn1=a2+kvn2a2modn2\underbrace{a_1 - k \cdot u \cdot n_1}_{\equiv a_1 \bmod n_1} = \underbrace{a_2 + k \cdot v \cdot n_2}_{\equiv a_2 \bmod n_2}

Assuming the solution is defined modulo lcm(n1,n2)\lcm(n_1, n_2), it follows that: xa1kun1a2+kvn2modlcm(n1,n2)x \equiv a_1 - k \cdot u \cdot n_1 \equiv a_2 + k \cdot v \cdot n_2 \mod \lcm(n_1, n_2)


Copyright © 2019 — 2021 Alexander Mayorov. All rights reserved.