[网络协议]近世代数——群笔记(1)

lemma 1

(Euclid’s Lemma) If $a|bc$ and $(a,b)=1$, then $a|c$

Proof: Since $(a,b)=1$, there exists $s,t\in \mathbb{N}$ such that $as+bt=1$. Hence, $c=c?1=c(as+bt)=a(cs)+t(bc)$. Since $a|a(cs),a|(bc)$, $a|c$.

lemma 2

If $(a,b)=1$, then the equation $ax\equiv c\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{b}$ is solvable.

Proof: Since $(a,b)=1$, $?s,t\in \mathbb{N}$, s.t. $as+bx=1$. Hence, $asc+bxc=c,$ $b|(a(sc)?c)$, that is $sc$ is a solution. In fact, all solutions are A : = { s c + b k ∣ k ∈ Z } A:=\{sc+bk|k\in\mathbb Z\} A:={sc+bk∣k∈Z}. Set $B$ are the set of all solutions of the equation. It’s clear that $A?B$. Next we will show $B?A$. If $x_0$ is a solution, then we get $a{x}_0\equiv c\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{b}$, $b|(a{x}_0?c)$, hence $b|(a{x}_0?c)+(as?c)?b|a(x_0?s)$. Since $(b,a)=1$, $b|(x_0?s)$, by Euclid’s Lemma. There exists some $k_0$ such that $s+b{k}_0=x_0$, hence $B?A$, $B=A$.

Chinese Reminder’s Theorem

If $(m,m^{\prime })=1$, then $x\equiv a\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{m}$ and $x\equiv b\mathrm{m}\mathrm{o}\mathrm{d}{\mathrm{m}}^{\prime }$ have solutions.

Proof: By lemma 2, the equation $x\equiv a\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{m}$ has solution $km+a,k\in \mathbb{Z}$. Insititude $km+a$ into $x\equiv b\mathrm{m}\mathrm{o}\mathrm{d}{\mathrm{m}}^{\prime }$, we get $km+a\equiv b\mathrm{m}\mathrm{o}\mathrm{d}{\mathrm{m}}^{\prime }$, $mk\equiv b?a\mathrm{m}\mathrm{o}\mathrm{d}{\mathrm{m}}^{\prime }$ for some $k$. Since $(m,m^{\prime })=1$, $?k_0\in \mathbb{Z}$, s.t. $m{k}_0\equiv b?a\mathrm{m}\mathrm{o}\mathrm{d}{\mathrm{m}}^{\prime }$. So $x_0=m{k}_0+a$ is a solution of equations.
Assume that $y$ is also a solution of equation, then $\{\begin{array}{l}y\equiv a\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{m}\\ y\equiv b\mathrm{m}\mathrm{o}\mathrm{d}{\mathrm{m}}^{\prime }\end{array}$, hence $\{\begin{array}{l}y?x_0\equiv 0\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{m}\\ y?x_0\equiv 0\mathrm{m}\mathrm{o}\mathrm{d}{\mathrm{m}}^{\prime }\end{array}$
Since $m|(y?x_0),m^{\prime }|(y?x_0),(m,m^{\prime })=1$, we have $m{m}^{\prime }|(y?x_0)(?)$.
So $?l\in \mathbb{Z}$, $y?x_0=lm{m}^{\prime },y=x_0+lm{m}^{\prime }$. Set X : = { s o l u t i o n s ? o f ? e q u a t i o n s } X:=\{\rm solutions~of~equations\} X:={solutions?of?equations}, Y : = { x 0 + m m ′ l ∣ l ∈ Z } Y:=\{x_0+mm'l|l\in\mathbb Z\} Y:={x0?+mm′l∣l∈Z}. Now we have got $X?Y$, next we show $Y?X$. $?x_0+m{m}^{\prime }l$, $x_0+m{m}^{\prime }l\equiv x_0\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{m}$, $x_0+m{m}^{\prime }l\equiv x_0\mathrm{m}\mathrm{o}\mathrm{d}{\mathrm{m}}^{\prime }$. Hence, $x_0+m{m}^{\prime }l$ is also a solution for any $l\in \mathbb{Z}$, $Y?X$, furthermore $X=Y$. Hence the solution of equations is { x 0 + m m ′ l ∣ l ∈ Z } \{x_0+mm'l|l\in\mathbb Z\} {x0?+mm′l∣l∈Z}.

proof of $(?)$: For $m|(y?x_0)$, $?u\in \mathbb{Z}$, s.t. $y?x_0=mu$. Since $m^{\prime }|(y?x_0)$, $m^{\prime }|mu$. Hence, $m^{\prime }|u$, by Euclid’s lemma. Hence, $m{m}^{\prime }|mu=y?x_0$.

An application of Chinese Remainder’s Theorem

Chinese Remainder’s Theorem is the key of the proof of the following statement:
If $(m,n)=1$, then ${\mathbb{Z}}_{mn}?{\mathbb{Z}}_m\times {\mathbb{Z}}_n$.
The detail will be ignored. Construct a map $?:\mathbb{Z}\to {\mathbb{Z}}_m\times {\mathbb{Z}}_n,a?([a{]}_m,[a{]}_n)$. In fact, $?$ is a bijection. Chinese Remainder’s theorem assures its surjection. $?a,b\in \mathbb{Z}$, we want to find a $x$ such that
$$\{\begin{array}{l}x\equiv a\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{m}\\ x\equiv b\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{n}\end{array}$$
Since $(m,n)=1$, by Chinese Remainder’s theorem, the equations have solutions, such as $x_0$, $[x_0{]}_{mn}?([x_0{]}_m,[x_0{]}_n)=([a{]}_m,[b{]}_n)$.