8.3 Сравнения первой степени.

Теорема 8.7:
Если $(a,m)=e$, то сравнение $az\equiv{b}\pod{m}$ имеет единственное решение.

Доказательство:
Так как $(a,m)=e$, то теоремам 6.3, 7.6, 8.1 и п.1 следствия 8.1 $$ \exists{u},v\in{R}:ua+vm=e\Rightarrow{u}a-b=(-v)m\Rightarrow{m}|(ua-e)\Rightarrow{u}a\equiv{e}\pod{m}\Rightarrow{a}(ub)\equiv{b}\pod{m}. $$ Таким образом $ub$ - решение сравнения $az\equiv{b}\pod{m}$. Докажем, что это решение едиственно.
Пусть существует два решения $z_1,z_2\in{R}$ сравнения $az\equiv{b}\pod{m}$. Тогда в следствии транзитивности отношения сравнимости и в силу п. 4 теоремы 8.2 $$ \begin{cases}az_1\equiv{b}\pod{m} \\ az_2\equiv{b}\pod{m}\end{cases}\Rightarrow{a}z_1\equiv{a}z_2\pod{m}\Rightarrow{z}_1\equiv{z}_2\pod{m} $$

Теорема 8.8:
Для любых $a,m\in{R}$ если $(a,m)=d$, то сравнение $$az\equiv{b}\pmod{m}\quad(1)$$ имеет решение тогда и только тогда, когда $d|b$.
При этом если $R=\mathbb{Z}$ то сравнение $(1)$ имеет $d$ различных решений.
Если $R=P[x]$, то сравнение $(1)$ имеет $|P|^d$ различных решений.

Доказательство:
$\Rightarrow)$ Если сравнение $(1)$ имеет решение, то $$\exists{z}_0\in{R}:az_0\equiv{b}\pod{m}\Rightarrow{m}|(az_0-b).$$ Так как $d=(a,m)$, то $$(d|a\,\wedge\,d|m)\Rightarrow(d|(az_0)\,\wedge\,d|(az_0-b))\Rightarrow{d}|b.$$ $\Leftarrow)$ Так как $d|a$, $d|b$, $d|m$, то по п. 3 теоремы 8.2 $$\forall{z}_0\in{R}\left(az_0\equiv{b}\pod{m}\Leftrightarrow\frac{a}{d}z_0\equiv\frac{b}{d}\;\left(\frac{m}{d}\right)\right).$$ Таким образом сравнение $$\frac{a}{d}z\equiv\frac{b}{d}\;\left(\frac{m}{d}\right)\quad(3)$$ равносильно сравнению $(1)$. По теореме 8.7 сравнение $(3)$ имеет единственное решение по модулю $m_0:=\frac{m}{d}$, обозначим его $z_0$. Таким образом множество всех решений сравнений $(1)$ и $(3)$ имеет вид $[z_0]_{m_0}:=\{z_0+m_0t\mid{t}\in{R}\}$. Найдем в $[z_0]_{m_0}$ подмножество попарно различных по модулю $m$ элементов максимальной мощности.
Для случая $R=\mathbb{Z}$ рассмотрим множество $B:=\{z_0+m_0t\mid{t}\in\overline{0,d-1}\}$.
Для случая $R=P[x]$ $B:=\{z_0(x)+m_0(x)r(x)\mid\deg{(r(x))}<\deg{(d(x))}\}$.
В обоих случаях верно

1. $B\subset[z_0]_{m_0}$,
2. Все элементы в $B$ попарно различны по модулю $m$.
3. $\forall{z}_1\in[z_0]_{m_0}\exists{z}_2\in{B}:z_1\equiv{z}_2\pod{m}$.

Замечание 8.3:
$$[r_0]_{m_0}=\bigcup_{r_1\in{B}}[z_1]_m.$$

Пример 8.3:
Решим сравнение $534z\equiv616\pod{100}$ над кольцом целых чисел $\mathbb{Z}$.
Так как $r_{100}(534)=34$, $r_{100}(616)=16$, то исходное сравнение равносильно сравнению $34z\equiv16\pod{100}$. Так как $(34,100)=2$, то исходное сравнение имеет два решения и равносильно сравнению $17z\equiv8\pod{50}$. Так как верно равенство $3\cdot17+(-1)\cdot50=1$, то из доказательства теоремы 8.7 следует, что $17\cdot3\cdot8\equiv8\pod{50}$. Таким образом $z_0=24$ - решение исходного сравнения. Тогда по теореме 8.8 множество различных решений исходного сравнения есть $\{24+50t\mid{t}\in\{0,1\}\}=\{24, 74\}$.

Пример 8.4:
Решим сравнение $$(x^3+1)z\equiv{x}^4+x^2\pmod{x^4+1}\quad(1)$$ над кольцом $GF(2)[x]$.
Так как $x^4+x^2=(x^4+1)+x^2+1$, то сравнение $(1)$ равносильно сравнению $$(x^3+1)z\equiv{x}^2+1\pmod{x^4+1}.\quad(2)$$ Осуществив последовательность делений по алгоритму Евклида, найдем НОД многочленов $x^3+1$ и $x^4+1$.

$x^4$ $+1$ $x^3+1$ $x^4$ $+x$ $x$ $x$ $+1$

$x^3$ $+1$ $x+1$ $x^3$ $+x^2$ $x^2+x+1$ $x^2$ $+1$ $x^2$ $+x$ $x$ $+1$ $x$ $+1$ $0$

Таким образом, $(x^3+1, x^4+1)=x+1$, тогда, так как $(x+1)|(x^2+1)$, то по теореме 8.8 сравнение $(2)$ имеет решение и оно равносильно сравнению $$\frac{x^3+1}{x+1}z\equiv\frac{x^2+1}{x+1}\;\left(\frac{x^4+1}{x+1}\right)$$ поделив

$x^3$ $+1$ $x+1$ $x^3$ $+x^2$ $x^2+x+1$ $x^2$ $+1$ $x^2$ $+x$ $x$ $+1$ $x$ $+1$ $0$

$x^2$ $+1$ $x+1$ $x^2$ $+x$ $x+1$ $x$ $+1$ $x$ $+1$ $0$

получим сравнение $$(x^2+x+1)z\equiv{x}+1\pmod{x^3+x^2+x+1},\quad(3)$$ которое по теореме 8.7 имеет единственное решение. Для нахождения решения найдем $u(x), v(x)$ такие, что $$u(x)(x^2+x+1)+v(x)(x^3+x^2+x+1)=1.$$ Несложно видеть, что подходят $u(x)=x$ и $v(x)=1$, тогда многочлен $z_0=u(x)(x+1)=x^2+x$ является решением сравнения $(3)$. Поскольку многочленов $r(x)\in{G}F(2)[x]$ таких, что $\deg{(r(x))}<\deg{(x+1)}$ только два $0$ и $1$, то по теореме 8.8 сравнение $(1)$ будет иметь два различных решения $z_0$ и $z_0+(x^3+x^2+x+1)=x^3+1$.

Теорема 8.9: Китайская теорема об остатаках.
Пусть $m_1,\ldots,m_k\in{R}\backslash\{0\}$ такие, что для любых различных $i,j\in\overline{1,k}$ $(m_i,m_j)=e$, $a_1,\ldots,a_k\in{R}$, тогда система сравнений $$ \begin{cases}z\equiv{a}_1\pmod{m_1} \\ \cdots \\ z\equiv{a}_k\pmod{m_k}\end{cases}\quad(4) $$ имеет единственное решение $z_0$ по модулю $m=m_1\cdots{m}_k$, при этом множество решений системы есть класс вычетов $[z_0]_m$.

Доказательство:

Докажем индукцией по $k$.

1. При $k=1$ следует из теоремы 8.7, так как $(e,m_1)=e$.
2. Пусть для любого $k\geq2$ утверждение верно для всех $s\in\overline{1,k-1}$ докажем, что оно верно при $s=k$.
   По предположению индукции система сравнений $$\begin{cases}z\equiv{a}_1\pmod{m_1} \\ \cdots \\ z\equiv{a}_{k-1}\pmod{m_{k-1}}\end{cases}\quad(5)$$ имеет одно решение $z_0$ по модулю $m_0=m_1\cdots{m}_{k-1}$ и множество решений системы сравнений $(5)$ имеет вид $$[z_0]_{m_0}=\{z_0+m_0t\mid{t}\in{R}\}.$$ Выясним какие элементы множества $[z_0]_{m_0}$ являются решением сравнения $z\equiv{a}_k\pod{m_k}$. $$ \forall{t}\in{R}(z_0+m_0t\equiv{a}_k\pod{m}_k\Leftrightarrow{m}_0t\equiv{a}_k-z_0\pod{m_k}). $$ Так как для любых различных $i,j\in\overline{1,k}$ $(m_i,m_j)=e$, то ${(m_0,m_k)=e}$, следовательно, по теореме 8.7 существует единственное решение сравнения $m_0t\equiv{a}_k-z_0\pod{m_k}$ относительно $t$. Обозначим это решение $[b]_{m_k}$, тогда множество решений системы сравнений $(4)$ имеет вид $$ \{z_0+m_0t\mid{t}\in[b]_{m_k}\}=\{z_0+m_0(b+m_kv)\mid{v}\in{R}\}=\{(z_0+m_0b)+mv\mid{v}\in{R}\}=[z_0+m_0b]_m $$