# 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$\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$
## 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
$\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$
