8. Кольца вычетов.

8.1 Сравнение по модулю.

Опредление 8.1:
Говорят, что элементы $a,b\in{R}$ сравнимы по модулю $m$, если $r_m(a)=r_m(b)$. При этом пишут $a\equiv{b}\pmod{m}$, или $a\equiv{b}\pod{m}$, или $a\underset{{}^m}{\equiv}b$.

Теорема 8.1:
$$\forall{a},b\in{R}(a\equiv{b}(m)\Leftrightarrow{m}|(a-b)).$$

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

Разделим с остатком элементы $a$ и $b$ на $m$, тогда существуют $q_1,q_2\in{R}$ такие, что $$ a=mq_1+r_m(a),\\ b=mq_2+r_m(b). $$ $\Rightarrow)$ $$ a\equiv{b}(m)\Rightarrow{r}_m(a)=r_m(b)\Rightarrow{a}-b=m(q_1-q_2)\Rightarrow{m}|(a-b) $$ $\Leftarrow)$ $$ a-b=m(q_1-q_2)+r_m(a)-r_m(b)\Rightarrow(m|(a-b)\Rightarrow{m}|(r_m(a)-r_m(b))) $$

1. Пусть $R=\mathbb{Z}$, тогда $$m|(r_m(a)-r_m(b))\Rightarrow(|m|\leq|r_m(a)-r_m(b)|\,\vee\,r_m(a)-r_m(b)=0).$$ Первая альтернатива не возможна, так как по определению остатка $$ (0\leq{r}_m(a)<|m|\,\wedge\,0\leq{r}_m(b)<|m|)\Rightarrow|r_m(a)-r_m(b)|\leq\max{\{r_m(a),r_m(b)\}}<|m|, $$ следовательно, верно второе $r_m(a)-r_m(b)=0$, то есть $r_m(a)=r_m(b)$.
2. Пусть $R=p[x]$. Так как по определению остатка $\deg{r_m(a)}<\deg{m}$, $\deg{r_m(b)}<\deg{m}$, то $\deg{(r_m(a)-r_m(b))}<\deg{m}$, следовательно, $$ m|(r_m(a)-r_m(b))\Rightarrow\exists{g}\in{P}[x]:r_m(a)-r_m(b)=gm\Rightarrow\deg{m}+\deg{g}=\deg{(r_m(a)-r_m(b))}<\deg{m}\Rightarrow \deg{g}=-\infty\Rightarrow{g}=0\Rightarrow{r}_m(a)=r_m(b). $$

Замечание 8.1:
Если элементы $m_1,m_2\in{R}\backslash\{0\}$ ассоциированы, то $$ \exists{u}\in{R}^*:m_1=um_2\Rightarrow(a\equiv{b}\pod{m_1}\Leftrightarrow{m}_1|(a-b)\Leftrightarrow{m}_2|(a-b)\Leftrightarrow{a}\equiv{b}\pod{m_2}). $$

1. Если $R=\mathbb{Z}$, то $R^*=\{-1,1\}$, то есть если модуль $m$ отрицателен, то существует положительный модуль $(-m)$ эквивалентный ему с точки зрения отношения сравнимости. Так что далее без ограничения общности будем считать, что если $m\in\mathbb{Z}$, то $m>0$.
2. Если $R=P[x]$, то по утверждению 7.3 для любого $m\in{P}[x]\backslash\{0\}$ существует ассоциированный с ним унитарный многочлен $m^*$ эквивалентный многочлену $m$ с точки зрения отношения сравнимости. Так что далее без ограничения общности будем считать, что если $m\in{P}[x]$, то $m$ - унитарен.

Замечание 8.2:
Отношение сравнимости по модулю $m$ является отношением эквивалентности.
Рефлексивность. $$\forall{a}\in{R}(a-a=0\Rightarrow{m}|(a-a)\Rightarrow{a}\equiv{a}\pod{m}).$$ Симметричность. $$\forall{a},b\in{R}(a\equiv{b}\pod{m}\Rightarrow{m}|(a-b)\Rightarrow{m}|(b-a)\Rightarrow{b}\equiv{a}\pod{m}).$$ Транзитивность. $$ \forall{a},b,c\in{R}(a\equiv{b}\pod{m}\,\wedge\,b\equiv{c}\pod{m}\Rightarrow{m}|(a-b)\,\wedge\,m|(b-c)\Rightarrow {m}|((a-b)+(b-c))\Rightarrow{m}|(a-c)\Rightarrow{a}\equiv{c}\pod{m}). $$

Теорема 8.2:
Пусть $a,b,c,d\in{R}$, тогда

1. $(a\equiv{b}\pod{m}\,\wedge\,c\equiv{d}\pod{m})\Rightarrow{a}c\equiv{b}d\pod{m}$,
2. $(a\equiv{b}\pod{m}\,\wedge\,c\equiv{d}\pod{m})\Rightarrow{a}+c\equiv{b}+d\pod{m}$,
3. Если $d\neq0$, $d|a$, $d|b$, $d|m$, то $$a\equiv{b}\pod{m}\Leftrightarrow\frac{a}{d}\equiv\frac{b}{d}\;\left(\frac{m}{d}\right).$$
4. Если $d|a$, $d|b$, $(d,m)=e$, то $$a\equiv{b}\pod{m}\Leftrightarrow\frac{a}{d}\equiv\frac{b}{d}\pod{m}.$$

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

1. По теореме 8.1 $$ \begin{cases}a\equiv{b}\pod{m} \\ c\equiv{d}\pod{m}\end{cases}\Rightarrow\begin{cases}m|(a-b) \\ m|(c-d)\end{cases}\Rightarrow\begin{cases}m|(ac-bc) \\ m|(bc-bd)\end{cases}\Rightarrow{m}|((ac-bc)+(bc-bd))\Rightarrow{m}|(ac-bd)\Rightarrow ac\equiv{b}d\pod{m} $$
2. По теореме 8.1
$$ \begin{cases}a\equiv{b}\pod{m} \\ c\equiv{d}\pod{m}\end{cases}\Rightarrow\begin{cases}m|(a-b) \\ m|(c-d)\end{cases}\Rightarrow{m}|((a-b)+(c-d))\Rightarrow{m}|((a+c)-(b+d))\Rightarrow{a}+c\equiv{b}+d\pod{m} $$
3. По теореме 8.1
$$ a\equiv{b}\pod{m}\Leftrightarrow{m}|(a-b)\Leftrightarrow\exists{q}\in{R}:a-b=mq\Leftrightarrow{d}\left(\frac{a}{d}-\frac{b}{d}\right)= d\left(\frac{m}{d}q\right), $$ так как $d\neq0$ и в кольце $R\in\{\mathbb{Z},{P}[x]\}$ нет делителей нуля, то последнее выражение эквивалентно $$ \frac{a}{d}-\frac{b}{d}=\frac{m}{d}q\Leftrightarrow\left.\frac{m}{d}\right|\left(\frac{a}{d}-\frac{b}{d}\right)\Leftrightarrow \frac{a}{d}\equiv\frac{b}{d}\;\left(\frac{m}{d}\right) $$
4. По теореме 8.1, п. 2 теоремы 6.7 и п. 2 теоремы 7.8 $$ a\equiv{b}\pod{m}\Leftrightarrow{m}|(a-b)\Leftrightarrow{m}\left|\left(d\left(\frac{a}{d}-\frac{b}{d}\right)\right)\right.\Leftrightarrow {m}\left|\left(\frac{a}{d}-\frac{b}{d}\right)\right.\Leftrightarrow\frac{a}{d}\equiv\frac{b}{d}\pod{m} $$

Следствие 8.1:
Пусть $a,b,c\in{R}$, $a\equiv{b}\pod{m}$ тогда

1. $ac\equiv{b}c\pod{m}$,
2. $a+c\equiv{b}+c\pod{m}$,
3. $\forall{k}\in\mathbb{N}(a^k\equiv{b}^k\pod{m})$

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

1. Следует из п. 1 теоремы 8.2, так как $c\equiv{c}\pod{m}$.
2. Следует из п. 2 теоремы 8.2, так как $c\equiv{c}\pod{m}$.
3. Докажем индукцией по $k$.
   1. При $k=1$ утверждение следует из условия.
   2. Пусть для любого $n\geq1$ утверждение верно при $k\in\overline{1,n}$, докажем, что оно верно при $k=n+1$.
      Так как $a\equiv{b}\pod{m}$ по условию, а $a^n\equiv{b}^n\pod{m}$ по предположению индукции, то по п. 1 теоремы 8.2 $$aa^n\equiv{b}b^n\pod{m}\Rightarrow{a}^{n+1}\equiv{b}^{n+1}\pod{m}.$$

Следствие 8.2:
Пусть $a,b\in{R}$, тогда

1. $a\equiv{r}_m(a)\pod{m}$,
2. $r_m(ab)=r_m(r_m(a)r_m(b))$,
3. $r_m(a+b)=r_m(r_m(a)+r_m(b))$,
4. $r_m(a^k)=r_m(r_m(a)^k)$.

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

1. По определению делимости и теореме 8.1 $$ \exists{q}\in{R}:a=mq+r_m(a)\Rightarrow{a}-r_m(a)=mq\Rightarrow{m}|(a-r_m(a))\Rightarrow{a}\equiv{r}_m(a)\pod{m}. $$
2. По пункту 1 $a\equiv{r}_m(a)\pod{m}$, $b\equiv{r}_m(b)\pod{m}$, тогда по п. 1 теоремы 8.2 $ab\equiv{r}_m(a)r_m(b)\pod{m}$, что эквивалентно доказываемому по опредлению сравнимости.
3. По пункту 1 $a\equiv{r}_m(a)\pod{m}$, $b\equiv{r}_m(b)\pod{m}$, тогда по п. 2 теоремы 8.2 $a+b\equiv{r}_m(a)+r_m(b)\pod{m}$, что эквивалентно доказываемому по определению сравнимости.
4. По пункту 1 $a\equiv{r}_m(a)\pod{m}$, тогда по п. 3 следствия 8.1 ${a^k\equiv{r}_m(a)^k\pod{m}}$, что эквивалентно доказываемому по определению сравнимости.

8.2 Классы вычетов.

Теорема 8.3:
Алгебра $(R/m;+,\cdot)$ является коммутативным кольцом в единицей.

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

1. Ассоциативность и коммутативнось операций $+$ и $\cdot$ в алгебре $(R/m;+,\cdot)$ следует из ассоциативности и коммутативности одноименных операций в кольце $R$.
2. Докажем для примера свойство дистрибутивности операции $\cdot$ относительно операции $+$. Пусть $[a],[b],[c]\in{R}/m$, тогда $$[a]([b]+[c])=[a][b+c]=[a(b+c)]=[ab+ac]=[ab][ac]=[a][b]+[a][c]$$
3. Нулем и единицей в $(R/m;+,\cdot)$ являются классы [0], [e], где $0,e\in{R}$ нуль и единица кольца $R$.
4. Так как для любого $[a]\in{R}/m$ $[a]+[-a]=[a-a]=[0]$, то класс $[-a]$ является противоположным к $[a]$.

Теоерма 8.4:

1. $[a]_m\in(R/m)^*\Leftrightarrow(a,m)=e$.
2. Класс $[a]\in{R}/m$ является делителем нуля тогда и только тогда, когда $(a,m)\neq{e}$ и $m\nmid{a}$.

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

1. По теоремам 8.1, 6.6 и 7.7 $$ [a]\in({R}/m)^*\Leftrightarrow\exists{b}\in{R}:[a][b]=[ab]=[e]\Leftrightarrow{a}b\equiv{e}\pod{m}\Leftrightarrow {m}|(e-ab)\Leftrightarrow\exists{c}\in{R}:e-ab=mc\Leftrightarrow{a}b+mc=e\Leftrightarrow(a,m)=e $$
2. $\Rightarrow)$ Докажем от противного.
   Предположим, что $(a,b)\neq{e}$, тогда по пункту 1 $[a]\in(R/m)^*$, следовательно, $[a]$ не делитель нуля.
   Предположим, что $m|a$, тогда $r_m(a)=0$ и $[a]=[r_m(a)]=[0]$, следовательно, $[a]$ не делитель нуля.
   $\Leftarrow)$ Положим $d:=(a,m)$, тогда $d|a$, $d|m$ и $$[a]\left[\frac{m}{d}\right]=\left[\frac{am}{d}\right]=\left[m\frac{a}{d}\right]=[0].$$ Если $m\nmid{a}$, то $r_m(a)\neq0$ и $[a]\neq[0]$.
   Если $d\neq{e}$, предположим, что $\frac{m}{d}\equiv0\pod{m}$, тогда $$\exists{q}\in{R}:\frac{m}{d}=mq=\frac{m}{d}dq\Rightarrow{d}q=1$$
   • Если $R=\mathbb{Z}$, то такое возможно только если $d=q=1$, так как $d>0$.
   • Если $R=P[x]$, то $\deg{d}+\deg{q}=0$, следовательно, $d=e$, так как $d$ примарный многочлен.
   Таким образом пришли к противоречию с предпосылкой, что $d\neq{e}$, следовательно, $\left[\frac{m}{d}\right]\neq[0]$. В итоге получили
   1. $[a]\left[\frac{m}{d}\right]=[0]$,
   2. $m\nmid{a}\Rightarrow[a]\neq[0]$,
   3. $(a,m)\neq{e}\Rightarrow\left[\frac{m}{d}\right]\neq[0]$,
   следовательно, $[a]$ делитель нуля.

Следствие 8.3:

1. Кольцо $\mathbb{Z}/m$ является полем тогда и только тогда, когда $m$ - простое число.
2. Кольцо $P[x]/f(x)$ является полем тогда и только тогда, когда многочлен $f(x)$ - не приводим.

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

1. Так как $\mathbb{Z}/m$ коммутативное кольцо с единицей, то оно будет полем тогда и только тогда, когда $(\mathbb{Z}/m)^*=(\mathbb{Z}/m)\backslash\{0\}$. По теореме 8.4 это эквивалентно $$ \forall{a}\in\overline{1,m-1}((a,m)=1)\Leftrightarrow\forall{a}\in\overline{2,m-1}(a\nmid{m})\Leftrightarrow\forall{a}\notin\{1,m\}(a\nmid{m}) $$ последнее выражение означает, что $m$ - простое.
2. Так как $P[x]/f(x)$ коммутативное кольцо с единицей, то оно будет полем тогда и только тогда, когда $(P[x]/f(x))^*=(P[x]/f(x))\backslash\{0\}$. По теореме 8.4 это эквивалентно $$ \forall{g}(x)\in{P}[x]\backslash\{0\}(\deg{(g(x))}<\deg{(f(x))}\Rightarrow(g(x),f(x))=e))\Leftrightarrow \forall{g}(x)\in{P}[x]\backslash\{0\}(0<\deg{(g(x))}<\deg{(f(x))}\Rightarrow{g}(x)\nmid{f}(x)) $$ последнее выражение означает, что $f(x)$ - не приводим.

Пример 8.1:
Если $p\in\mathbb{Z}$ простое число, то кольцо вычетов $\mathbb{Z}/p$ является полем мощности $|\mathbb{Z}/p|=p$. Если при этом многочлен $f(x)\in(\mathbb{Z}/p)[x]$ такой, что $\deg{(f(x))}=k>0$ и $f(x)$ - не приводим, то кольцо вычетов $(\mathbb{Z}/p)[x]/f(x)$ является полем содержащим классы вычетов образованные многочленами степени не больше $k-1$, следовательно, $|(\mathbb{Z}/p)[x]/f(x)|=|\mathbb{Z}/p|^k=p^k$.
Например, пусть $p=2$, $f(x)=x^2+x+[1]_2\in(\mathbb{Z}/2)[x]$. Следовательно, так как $f([0]_2)=[0]_2+[0]_2+[1]_2=[1]_2$, $f([1]_2)=[1]_2+[1]_2+[1]_2=[1]_2$, то по теореме 7.3 многочлен $f(x)$ степени 2 не имеет делителей степени 1, тогда многочлен $f(x)$ не приводим над $\mathbb{Z}/2$. Тогда кольцо вычетов $$(\mathbb{Z}/2)[x]/f(x)=\{[0]_{f(x)}, [1]_{f(x)}, [x]_{f(x)}, [x+1]_{f(x)}\}$$ является полем мощности $p^2=2^2=4$.
Пусть $p=3$, $f(x)=x^2+[1]_3\in(\mathbb{Z}/3)[x]$. Тогда, так как $f([0]_3)=[1]_3$, $f([1]_3)=[1]_3+[1]_3=[2]_3$, $f([2]_3)=[2]_3[2]_3+[1]_3=[1]_3+[1]_3=[2]_3$, то многочлен $f(x)$ не приводим над $\mathbb{Z}/3$. Тогда кольцо вычетов $(\mathbb{Z}/3)[x]/f(x)$ является полем мощности $p^2=3^2=9$.

Следствие 8.2:
Функцией Эйлера называется функция $\varphi(m):\mathbb{N}\to\mathbb{N}$ такая, что для любого $m\in\mathbb{N}$ $\varphi(m)=|\{a\in\overline{1,m}\mid(a,m)=1\}|$.
То есть $\varphi(m)$ равно количеству чисел меньших $m$ и взаимнопростых с $m$.

Следствие 8.4:
$$\forall{m}\in\mathbb{N}(|(\mathbb{Z}/m)^*|=\varphi(m))$$

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

Следует из теоремы 8.4

Теорема 8.5: Свойства функции Эйлера.

1. Если $p\in\mathbb{N}$ - простое, то $\varphi(p)=p-1$.
2. Если $p\in\mathbb{N}$ - простое, то $\varphi(p^k)=p^k-p^{k-1}=p^{k-1}(p-1)$.
3. $\forall{m}_1,m_2\in\mathbb{N}((m_1,m_2)=1\Rightarrow\varphi(m_1m_2)=\varphi(m_1)\varphi(m_2))$.
4. Если $m\in\mathbb{N}$ и $m=p_1^{k_1}\cdots{p}_s^{k_s}$ - каноническое разложение числа $m$, то
$$\varphi(m)=m\prod_{i=1}^s\left(1-\frac1{p_i}\right).$$

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

1. Докажем от противного, что для любого $a\in\overline{2,p-1}$ $(a,p)=1$. Предположим, что существует $a\in\overline{2,p-1}$ такое, что $(a,p)=d>1$, тогда $d|a$, следовательно, $1<d\leq{a}<p$. Следовательно, найдено $d$ такое, что $d|p$ и $d\notin\{1,p\}$, то есть $p$ не простое. Получено противоречие. Таким образом для любого $a\in\overline{1,p-1}$ $(a,p)=1$, то есть $\varphi(p)=p-1$, так как по понятным причинам, для любого $m\in\mathbb{N}$ $\varphi(m)\leq{m}-1$.
2. Пусть $a\in\overline{1,p^k}$, тогда по теореме 6.11 $(a,p)>1$ тогда и только тогда, когда число $a$ содержит в своем каноническом разложении число $p$. То есть существует натуральное число $q$ такое, что $a=pq$. С другой стороны, $a=pq\leq{p}^k$ тогда и только тогда, когда $q\in\overline{1,p^{k-1}}$. Следовательно, $\varphi(p^k)=|\overline{1,p^k}|-|\overline{1,p^{k-1}}|=p^k-p^{k-1}$.
3. Будет доказано позже при изучении теории групп (следствие 10.4).
4. По пунктам 3 и 2 $$ \varphi(m)=\varphi(p_1^{k_1}\cdots{p}_s^{k_s})=\varphi(p_1^{k_1})\cdots\varphi(p_s^{k_s})=p_1^{k_1-1}(p_1-1)\cdots{p}_s^{k_s-1}(p_s-1)= p_1^{k_1}\cdots{p_s}^{k_s}\left(1-\frac1{p_1}\right)\cdots\left(1-\frac1{p_s}\right)=m\prod_{i=1}^s\left(1-\frac1{p_i}\right) $$

Теорема 8.6: Теорема Эйлера-Ферма.
$$\forall{a}\in\mathbb{Z}\,\forall{m}\in\mathbb{N}((a,m)=1\Rightarrow{a}^{\varphi(m)}\equiv1\pmod{m}).$$

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

Так как по следствию 8.4 $|(\mathbb{Z}/m)^*|=\varphi(m)$, можем положить $(\mathbb{Z}/m)^*=\{[a_1],\ldots,[a_{\varphi(m)}]\}$. Так как $(a,m)=1$, то по теореме 8.4 $a\in(\mathbb{Z}/m)^*$, тогда $$ \forall{i}\in\overline{1,\varphi(m)}([a][a_i]=[aa_i]\in(\mathbb{Z}/m)^*)\Rightarrow{A}:=\{[aa_i]\mid{i}\in\overline{1,\varphi(m)}\}\subset(\mathbb{Z}/m). $$ С другой стороны, так как $[a]\in(\mathbb{Z}/m)^*$, то $$ \forall{i},j\in\overline{1,\varphi(m)}([aa_i]=[aa_j]\Rightarrow[a][a_i]=[a][a_j]\Rightarrow[a_i]=[a_j])\Rightarrow|A|=\varphi(m)=|(\mathbb{Z}/m)^*| $$ Таким образом $A=(\mathbb{Z}/m)^*$, тогда $$ \prod_{i=1}^{\varphi(m)}[a_i]=\prod_{i=1}^{\varphi(m)}[aa_i]=[a^{\varphi(m)}]\prod_{i=1}^{\varphi(m)}[a_i] $$ Так как произведение обратимых элементов обратимо, то можно домножить полученное равенство на элемент обратный к $\prod_{i=1}^{\varphi(m)}[a_i]$. Тогда получим $[a^{\varphi(m)}]=[1]$, то есть ${a}^{\varphi(m)}\equiv1\pod{m}$.

Следствие 8.5: Малая теорема Ферма.
Если $p$ - простое, $a\in\mathbb{Z}$, $(a,p)=1$, то $a^{p-1}\equiv1\pmod{p}$.

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

Следует из теоремы 8.6 и п. 1 теоремы 8.5.

Следствие 8.6:
Если $p$ - простое, $a\in\mathbb{Z}$, то $a^p\equiv{a}\pmod{p}$.

Доказательство:
Если $(a,p)=1$, то утверждение следутет из следствия 8.5.
Если $(a,p)\neq1$, то $p|a$, тогда $a\equiv0\pod{p}$, и $a^p\equiv0\pod{p}$

Пример 8.2:
Используя полученные результаты вычислим $A:=r_{35}(128^{956})$ - остаток от деления числа $128^{956}$ на $35$.
Так как $r_{35}(128)=23$, то по п. 4 следствия 8.2 $A=r_{35}(23^{956})$.
Так как $(35,23)=1$, можем применить теорему 8.6, тогда $23^{\varphi(35)}\equiv1\pod{35}$, где $\varphi(35)=\varphi(5\cdot7)=\varphi(5)\varphi(7)=4\cdot6=24$, то есть $23^{24}\equiv1\pod{35}$.
Поделив $956$ на $24$ получим $956=24\cdot39+20$, то есть $23^{956}=(23^{24})^{39}\cdot23^{20}$. По п. 1 теоремы 8.2 можем возвести сравнение $23^{24}\equiv1\pod{35}$ в $39$ степень, а потом домножить на $23^{20}$, тогда получим $23^{956}=(23^{24})^{39}\cdot23^{20}\equiv23^{20}\pod{35}$. Таким образом $A=r_{35}(23^{20})$.
Далее $23^{20}=(23^2)^{10}$, $23^2=529=35\cdot15+4$, то есть $23^2\equiv4\pod{35}$, возводя это сравнение в $10$ степень получим $23^{20}\equiv4^{10}\pod{35}$. Таким образом $$A=r_{35}(4^{10})=r_{35}(1024^2)=r_{35}((r_{35}(1024))^2)=r_{35}(9^2)=r_{35}(81)=11.$$

previous contents next