Congruent

Define

If $$$a,b$$$ are two integers and their difference is divisible by some natural number $$$m$$$, then $$$a$$$ is said to be congruent to $$$b$$$ with respect to the modulus $$$m$$$, or $$$a$$$ is congruent to $$$b$$$ with respect to the modulus $$$m$$$, denoted $$$a \equiv b \pmod m$$$. This means that $$$a - b = m \times k$$$ ($$$k$$$ is some integer).
For example, $$$32 \equiv 2 \pmod 5$$$, when $$$k$$$ is $$$6$$$.

For integers $$$a$$$, $$$b$$$, and $$$m$$$, $$$a$$$ and $$$b$$$ are said to be congruent in the sense of $$$\bmod m$$$ if $$$a \bmod m = b \bmod m$$$, denoted $$$a \equiv b \pmod m$$$.

It is easily obtained from the concept:
1. if $$$a \equiv b \pmod m$$$, then it is fixed that $$$\sqsupseteq k,l,c \in \mathbb{Z},a = km + c,b = lm + c$$$; 2. if $$$a \equiv b \pmod m$$$, if and only if $$$m \mid (a - b)$$$.

$$$\because a \equiv b \pmod m$$$
$$$\therefore \sqsupseteq k,l,c \in \mathbb{Z},a = km + c,b = lm + c$$$
$$$\therefore m \mid (a - b) \Rightarrow m \mid (km + c - lm - c) \Rightarrow m \mid (km - lm) \Rightarrow m \mid (k - l)m$$$
$$$\therefore The conclusion is valid$$$

characteristic

Self-reflexivity: $$$a \equiv a \pmod m$$$.

Symmetry: if $$$a \equiv b \pmod m$$$, then $$$b \equiv a \pmod m$$$.

Transitive: if $$$a \equiv b \pmod m,b \equiv c \pmod m$$$, then $$$a \equiv c \pmod m$$$.

Same additivity: if $$$a \equiv b \pmod m$$$, then $$$a + c \equiv b + c \pmod m$$$.

$$$\because a \equiv b \pmod m$$$
$$$\therefore \sqsupseteq k,l,\alpha \in \mathbb{Z},a = km + \alpha,b = lm + \alpha$$$
$$$\therefore a + c \equiv b + c \pmod m$$$
$$$\Rightarrow km + \alpha + c \equiv lm + \alpha + c \pmod m$$$
$$$\Rightarrow km + (a + c) \equiv lm + (a + c) \pmod m$$$
$$$The conclusion is valid$$$

Simultaneity: if $$$a \equiv b \pmod m$$$, then $$$a \times c \equiv b \times c \pmod m$$$;
If $$$a \equiv b \pmod m,c \equiv d \pmod m$$$, then $$$a \times c \equiv b \times d \pmod m$$$.

$$$\because a \equiv b \pmod m,c \equiv d \pmod m$$$
$$$\therefore \sqsupseteq k,l,c \in \mathbb{Z},a = km + c,b = lm + c$$$
$$$\because c \equiv d \pmod m$$$
$$$\therefore \sqsupseteq k,l,\gamma \in \mathbb{Z},c = \alpha m + \gamma,d = \beta m + \gamma$$$
$$$\therefore ac \equiv bd \pmod m$$$
$$$\Leftrightarrow (km + c)(\alpha m + \gamma) \equiv (lm + c)(\beta m + \gamma) \pmod m$$$
$$$\Leftrightarrow k\alpha m^2 + c\alpha m + c\gamma \equiv l\beta m^2 + \gamma m + c\gamma \pmod m$$$
$$$The conclusion is valid$$$

Does not satisfy simultaneous divisibility, but if $$$\gcd(c,m) = 1$$$, then there is $$$a \equiv b \pmod m$$$ when $$$a \times c \equiv b \times c \pmod m$$$.

$$$ac \equiv bc \pmod m$$$
$$$\Rightarrow c(a - b) \equiv 0 \pmod m$$$
$$$\Rightarrow c \% m \times (a - b) \% m = 0$$$
$$$\Rightarrow m \mid c \text{或}m \mid (a - b)$$$
$$$\because (m,c) = 1$$$
$$$\therefore m \mid (a - b)$$$
$$$a \equiv b \pmod m$$$
$$$The conclusion is valid$$$

Idempotence: if $$$a \equiv m \pmod m$$$, then $$$a^n \equiv b^n \pmod m$$$.

Certification 1
$$$\because a^n \equiv b^n \pmod m \Leftrightarrow \overbrace{a \times a \times \cdots \times a}^{a^n} \equiv \overbrace{b \times b \times b \times \cdots \times b}^{b^n} \pmod m$$$
$$$\therefore a \equiv b \pmod m$$$
$$$\because a \equiv b \pmod m$$$
$$$\therefore a \times a \equiv b \times b \pmod m\ \ conclude 6$$$
$$$\because a \times a\equiv b \times b \pmod m,a \equiv m \pmod m$$$
$$$\therefore (a \times a)\times a \equiv (b \times b)\times b \pmod m\ \ conclude 6$$$
$$$\cdots$$$
$$$The above conclusion can be obtained by using conclusion 6 only several times$$$

Certification 2
$$$\because \sqsupseteq k,l,c \in \mathbb{Z},a = km + c,b = lm + c$$$
$$$\therefore when b = 2, (km + c)^2 \Leftrightarrow (km)^2 + 2kmc + c^2,(lm + c)^2 \Leftrightarrow (lm)^2 + 2lmc + c^2$$$
$$$\therefore when b = 3, (km + c)^3 \Leftrightarrow (km)^3 + 3(km)^2c + 3kmc^2 + c^3,(lm + c)^3 \Leftrightarrow (lm)^3 + 3(lm)^2c + 3lmc^2 + c^3$$$
$$$\cdots$$$
$$$According\ to\ the\ quadratic\ term\ theorem,\ the\ coefficient\ expansion\ of\ the\ constant\ term\ of\ is\ c^n,\ that\ means\ (a^n) \pmod m = (a \bmod m)^n,(b^n) \bmod m = (b \bmod m)^n$$$
$$$\because a \equiv b \pmod m$$$
$$$\therefore a^n \equiv a^n \pmod m$$$

Corollary 1: $$$a \times b \pmod k = (a \bmod k)\times (b \bmod k)\bmod k$$$.
Corollary 2: If $$$\gcd(p, q) = 1$$$, $$$a \bmod p = x,a \bmod q = x$$$，则 $$$a \bmod (p \times q) = x$$$.

$$$\because \gcd(p, q) = 1,\ a \bmod p = x,a \bmod q = x$$$
$$$\therefore There\ must\ exist\ an\ integer\ s,\ t,\ makes\ a = s \times p + x,a = t \times q +x$$$
$$$\therefore s \times p = t \times q$$$
$$$\because t\ is\ an\ integer,\gcd(p, q) = 1,\ move\ q to\ the\ left$$$
$$$\therefore q \mid s,\ that\ means\ there\ is\ an\ integer\ r\ which\ can\ makes\ s = r \times q$$$
$$$\therefore a = r \times q \times p + x,\ a \bmod (p \times q) = x$$$

Certification 1
$$$a \bmod q = x,a \bmod p = x$$$
$$$\therefore \sqsupseteq k,l \in \mathbb{Z},a = kq + x,b = lq + x$$$
$$$\therefore q \mid (a -x),p \mid (a -x)$$$
$$$\therefore (a -x) = cm(p, q)$$$
$$$\therefore \sqsupseteq \alpha \in \mathbb{Z},(a - x) = \alpha pq + x$$$
$$$a = \alpha pq + x$$$
$$$a \bmod pq = x$$$

Certification 2
$$$\because a \bmod q = x,a \bmod p$$$
$$$\sqsupseteq k,l \in \mathbb{Z},a = kq + x = lp + x$$$
$$$\therefore kq + x = lp + x \Rightarrow kq = lp$$$
$$$\because \gcd(q,p) = 1$$$
$$$\therefore \sqsupseteq r \in \mathbb{Z},k = rp$$$
$$$\therefore a= rpq + x$$$
$$$\therefore a \bmod pq = x$$$