<filename>docs/1st term/Algebra/Aut_Mid/Body/P1_s.tex<gh_stars>0
\section{1 Диофантовы уравнения}
	\subsection{1 вариант}
		1)\\
		Рассмотрим $ax+by = k$, разделим все, если возможно(иначе корней нет), на $\gcd(a,b)$,\\
		Получим $\frac{a}{\gcd(a,b)} x+ \frac{b}{\gcd(a,b)} y = \frac{k}{\gcd(a,b)} \ = \ a_0 x + b_0 y = k_0$, теперь $\gcd(a_0,b_0) = 1$\\ 
		По алгоритму евклида найдем 1 пару $a_1,\ b_1$ при которой равенство выполнено, тогда все решения можно записать как:\\
		\begin{gather*}
			\begin{cases}
				x_n \ = \ a_1 + n \cdot \frac{a}{\gcd(a,b)} \ = \ a_1 + n \cdot a_0\\
				y_n \ = \ b_1 - n \cdot \frac{b}{\gcd(a,b)} \ = \ b_1 - n \cdot b_0
			\end{cases}
			\quad n \in \mathbb{Z}\\
			\text{gcd(a,b) \ = \ НОД(a,b) \ = \ (a,b)}
		\end{gather*}
		2)\\
		Рассмотрим $ax+by+cz = k$. Если $k \mod \gcd(a, b, c) = 0$, то у уравнения есть решения, иначе их нет.\\
		Пусть $p = \gcd(a, b)$, и $a^{\star} = \frac{a}{p} \quad b^{\star} = \frac{b}{p}$\\
		Тогда решим уравнение $a^{\star} u + b^{\star} v = c$ -- его решения $u_0$ и $v_0$ (по (1) пункту)\\
		$z_0$ и $t_0$ -- решения $cz + pt = d$ (по (1) пункту)\\
		$x_0$ и $y_0$ -- решения $a^{\star} x + b^{\star} y = t_0$ (по (1) пункту)\\
		Тогда решения системы это:
		\begin{gather*}
			\begin{cases}
				x \ = \ x_0 + b^{\star} k - u_0 m \\
				y \ = \ y_0 - a^{\star} k - v_0 m \\
				z \ = \ z_0 + p m
			\end{cases}
			\\
			k, m \in \mathbb{Z}
		\end{gather*}

	\subsection{2 вариант}
		\begin{gather*}
			ax + by = k,\ c = (a, b)\\
			\frac{a}{c} \cdot cx + \frac{b}{c} \cdot cy = k,\ a_0 = \frac{a}{c},\ b_0 = \frac{b}{c}\\
			c(\frac{a}{c} \cdot x + \frac{b}{c} \cdot y) = k\\
			c(a_0 x + b_0 y) = k \ \Rightarrow c | k,\ k_0 = \frac{k}{c}\\
			a_0 x + b_0 y = k_0\\
			a_0 x_1 + b_0 y_1 = 1 \Leftrightarrow (a_0, b_0) = 1\\
			x = x_1 \cdot k_0 + b_0 \cdot n\\
			y = y_1 \cdot k_0 - a_0 \cdot n\\
		\end{gather*}
		\\
		$ax + by + cz = k,\ d = (a, b)$\\
		Заметим, что $((a, b), c) = (a, b, c)$\\
		$k_0 \cdot (a, b) = ax + by \ \Rightarrow \ (a, b)k_0 + cz = k$ Свели к предыдущей задаче.
		
		
\newpage
\section{2}
	\subsection{1 вариант}
		Рассмотрим поле $L$ разложения многочлена $x^{p^n} - x$ над полем $\mathbb{Z}_p$.\\
		У данного многочлена нет кратных корней (так как его производная равна $-1$ и взаимно просто с самим многочленом), поэтому все корни многочлена $x^{p^n} - x$, лежащие в $L$, различны.\\
		Колическтво таких корней равно $q = p^n$.\\ 
		Докажем, что множество образует поле.\\ 
		Действительно, если $a^q = a$; $b^q = b$, то $(ab)^q = ab$. Значит множество замкнуто по умножению, тоже самое для сложения. $\Rightarrow$ нашли искомое поле из $p^n$ элементов.\\
		Докажем, что все поля из $p^n$ элементов изоморфны.\\
		Как мы показали выше, поле из $p^n$ элементов обязательно является полем разложения многочлена $x^{p^n} - x$. Так мы доказали, что поле разложение многочлена единственно с точностью до изоморфизма, единственность доказана полностью.
		
	\subsection{2 вариант}
		Докажем что все конечные поля одинакового порядка изоморфны\\
		Рассмотрим поля $A$ и $B$ порядка $p^n$. Пусть $a \in A$ и $b \in B$ -- примитивные элементы полей. Ненулевых элементов в $A$ и $B$ ровно $p^n - 1$. \\
		У многочлена $x^{p^n - 1} - 1$ ровно $p^n - 1$ ненулевых корней. Все эти корни различны и лежат как в $A$, так и в $B$. Тогда, так как порядки полей совпадают, то некий $\alpha \in A$ перешел в $\beta \in B$. И тогда $\alpha^k = \beta$, а это отоношение задает изоморфизм полей.
		\\
		2:
		\begin{center}
			\begin{tabular}{|c|c|c|}
				\hline
				$+ $&$ 0 $&$ 1 $\\
				\hline
				$0 $&$ 0 $&$ 1 $\\
				\hline
				$1 $&$ 1 $&$ 0 $\\
				\hline
			\end{tabular}
		\end{center}
		\begin{center}
			\begin{tabular}{|c|c|c|}
				\hline
				$\times $&$ 0 $&$ 1 $\\
				\hline
				$0 $&$ 0 $&$ 0 $\\
				\hline
				$1 $&$ 0 $&$ 1 $\\
				\hline
			\end{tabular}
		\end{center}		
		4:
		\begin{center}
			\begin{tabular}{|c|c|c|c|c|}
				\hline
				$+ $&$ 0 $&$ 1 $&$ x $&$ x+1 $\\
				\hline
				$0 $&$ 0 $&$ 1 $&$ x $&$ x+1$\\
				\hline
				$1 $&$ 1 $&$ 0 $&$ x+1 $&$ x$\\
				\hline
				$x $&$ x $&$ x+1 $&$ 0 $&$ 1$\\
				\hline
				$x+1 $&$ x+1 $&$ x $&$ 1 $&$ 0$\\
				\hline
			\end{tabular}
		\end{center}
		\begin{center}
			\begin{tabular}{|c|c|c|c|c|}
				\hline
				$\times $&$ 0 $&$ 1 $&$ x $&$ x+1 $\\
				\hline
				$0 $&$ 0 $&$ 0 $&$ 0 $&$ 0$\\
				\hline
				$1 $&$ 0 $&$ 1 $&$ x $&$ x+1$\\
				\hline
				$x $&$ 0 $&$ x $&$ 0 $&$ 1$\\
				\hline
				$x+1 $&$ 0 $&$ x+1 $&$ 1 $&$ 0$\\
				\hline
			\end{tabular}
		\end{center}	
		8:
		\begin{center}
			\begin{tabular}{|c|c|c|c|c|c|c|c|c|}
				\hline
				$+ $&$ 0 $&$ 1 $&$ x $&$ x+1 $&$ x^2 $&$ x^2+1 $&$ x^2+x $&$ x^2+x+1$\\
				\hline
				$0 $&$ 0 $&$ 1 $&$ x $&$ x+1 $&$ x^2 $&$ x^2+1 $&$ x^2+x $&$ x^2+x+1$\\
				\hline
				$1 $&$ 1 $&$ 0 $&$ x+1 $&$ x $&$ x^2+1 $&$ x^2 $&$ x^2+x+1 $&$ x^2+x$\\
				\hline
				$x $&$ x $&$ x+1 $&$ 0 $&$ 1 $&$ x^2+x $&$ x^2+x+1 $&$ x^2 $&$ x^2+1$\\
				\hline
				$x+1 $&$ x+1 $&$ x $&$ 1 $&$ 0 $&$ x^2+x+1 $&$ x^2+x $&$ x^2+1 $&$ x^2$\\
				\hline
				$x^2 $&$ x^2 $&$ x^2+1 $&$ x^2+x $&$ x^2+x+1 $&$ 0 $&$ 1 $&$ x $&$ x+1$\\
				\hline
				$x^2+1 $&$ x^2+1 $&$ x^2 $&$ x^2+x+1 $&$ x^2+x $&$ 1 $&$ 0 $&$ x+1$&$ x$\\
				\hline
				$x^2+x $&$ x^2+x $&$ x^2+x+1 $&$ x^2 $&$ x^2+1 $&$ x $&$ x+1 $&$ 0 $&$ 1$\\
				\hline
				$x^2+x+1 $&$ x^2+x+1 $&$ x^2+x $&$ x^2+1 $&$ x^2 $&$ x+1 $&$ x $&$ 1 $&$ 0$\\
				\hline
			\end{tabular}
		\end{center}
		\begin{center}
			\begin{tabular}{|c|c|c|c|c|c|c|c|c|}
				\hline
				$\times $&$ 0 $&$ 1 $&$ x $&$ x+1 $&$ x^2 $&$ x^2+1 $&$ x^2+x $&$ x^2+x+1$\\
				\hline
				$0 $&$ 0 $&$ 0 $&$ 0 $&$ 0 $&$ 0 $&$ 0 $&$ 0 $&$ 0$\\
				\hline
				$1 $&$ 0 $&$ 1 $&$ x $&$ x+1 $&$ x^2 $&$ x^2+1 $&$ x^2+x $&$ x^2+x+1$\\
				\hline
				$x $&$ 0 $&$ x $&$ x^2 $&$ x^2+x $&$ x+1 $&$ 1 $&$ x^2+x+1 $&$ x^2+1$\\
				\hline
				$x+1 $&$ 0 $&$ x+1 $&$ x^2+x $&$ x^2+1 $&$ x^2+x+1 $&$ x^2 $&$ 1 $&$ x$\\
				\hline
				$x^2 $&$ 0 $&$ x^2 $&$ x+1 $&$ x^2+x+1 $&$ x^2+x $&$ x $&$ x^2+1 $&$ 1$\\
				\hline
				$x^2+1 $&$ 0 $&$ x^2+1 $&$ 1 $&$ x^2 $&$ x $&$ x^2+x+1 $&$ x+1 $&$ x^2+x$\\
				\hline
				$x^2+x $&$ 0 $&$ x^2+x $&$ x^2+x+1 $&$ 1 $&$ x^2+1 $&$ x+1 $&$ x $&$ x^2$\\
				\hline
				$x^2+x+1 $&$ 0 $&$ x^2+x+1 $&$ x^2+1 $&$ x $&$ 1 $&$ x^2+x $&$ x^2 $&$ x+1$\\
				\hline
			\end{tabular}
		\end{center}	
		3:
		\begin{center}
			\begin{tabular}{|c|c|c|c|}
				\hline
				$+ $&$ 0 $&$ 1 $&$ 2$\\
				\hline
				$0 $&$ 0 $&$ 1 $&$ 2$\\
				\hline
				$1 $&$ 1 $&$ 2 $&$ 0$\\
				\hline
				$2 $&$ 2 $&$ 0 $&$ 1$\\
				\hline
			\end{tabular}
		\end{center}
		\begin{center}
			\begin{tabular}{|c|c|c|c|}
				\hline
				$\times $&$ 0 $&$ 1 $&$ 2$\\
				\hline
				$0 $&$ 0 $&$ 0 $&$ 0$\\
				\hline
				$1 $&$ 0 $&$ 1 $&$ 2$\\
				\hline
				$2 $&$ 0 $&$ 2 $&$ 1$\\
				\hline
			\end{tabular}
		\end{center}
		9:
		\begin{center}
			\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|}
				\hline
				$+ $&$ 0 $&$ 1 $&$ 2 $&$ x $&$ x+1 $&$ x+2 $&$ 2x $&$ 2x+1 $&$ 2x+2$\\
				\hline
				$0 $&$ 0 $&$ 1 $&$ 2 $&$ x $&$ x+1 $&$ x+2 $&$ 2x $&$ 2x+1 $&$ 2x+2$\\
				\hline
				$1 $&$ 1 $&$ 2 $&$ 0 $&$ x+1 $&$ x+2 $&$ x $&$ 2x+1 $&$ 2x+2 $&$ 2x$\\
				\hline
				$2 $&$ 2 $&$ 0 $&$ 1 $&$ x+2 $&$ x $&$ x+1 $&$ 2x+2 $&$ 2x+1 $&$ 2x$\\
				\hline
				$x $&$ x $&$ x+1 $&$ x+2 $&$ 2x $&$ 2x+1 $&$ 2x+2 $&$ 0 $&$ 1 $&$ 2$\\
				\hline
				$x+1 $&$ x+1 $&$ x+2 $&$ x $&$ 2x+1 $&$ 2x+2 $&$ 2x $&$ 1 $&$ 2 $&$ 0$\\
				\hline
				$x+2 $&$ x+2 $&$ x $&$ x+1 $&$ 2x+2 $&$ 2x $&$ 2x+1 $&$ 2 $&$ 0 $&$ 1$\\
				\hline
				$2x $&$ 2x $&$ 2x+1 $&$ 2x+2 $&$ 0 $&$ 1 $&$ 2 $&$ x $&$ x+1 $&$ x+2$\\
				\hline
				$2x+1 $&$ 2x+1 $&$ 2x+2 $&$ 2x $&$ 1 $&$ 2 $&$ 0 $&$ x+1 $&$ x+2 $&$ x$\\
				\hline
				$2x+2 $&$ 2x+2 $&$ 2x $&$ 2x+1 $&$ 2 $&$ 0 $&$ 1 $&$ x+2 $&$ x $&$ x+1$\\
				\hline
			\end{tabular}
		\end{center}
		\begin{center}
			\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|}
				\hline
				$\times $&$ 0 $&$ 1 $&$ 2 $&$ x $&$ x+1 $&$ x+2 $&$ 2x $&$ 2x+1 $&$ 2x+2$\\
				\hline
				$0 $&$ 0 $&$ 0 $&$ 0 $&$ 0 $&$ 0 $&$ 0 $&$ 0 $&$ 0 $&$ 0$\\
				\hline
				$1 $&$ 0 $&$ 1 $&$ 2 $&$ x $&$ x+1 $&$ x+2 $&$ 2x $&$ 2x+1 $&$ 2x+2$\\
				\hline
				$2 $&$ 0 $&$ 2 $&$ 1 $&$ 2x $&$ 2x+2 $&$ 2x+1 $&$ x $&$ x+2 $&$ x+1$\\
				\hline
				$x $&$ 0 $&$ x $&$ 2x $&$ 2 $&$ x+2 $&$ 2x+2 $&$ 1 $&$ x+1 $&$ 2x+1$\\
				\hline
				$x+1 $&$ 0 $&$ x+1 $&$ 2x+2 $&$ x+2 $&$ 2x $&$ 1 $&$ 2x+1 $&$ 2 $&$ x$\\
				\hline
				$x+2 $&$ 0 $&$ x+2 $&$ 2x+1 $&$ 2x+2 $&$ 1 $&$ x $&$ x+1 $&$ 2x $&$ 2$\\
				\hline
				$2x $&$ 0 $&$ 2x $&$ x $&$ 1 $&$ 2x+1 $&$ x+1 $&$ 2 $&$ 2x+2 $&$ x+2$\\
				\hline
				$2x+1 $&$ 0 $&$ 2x+1 $&$ x+2 $&$ x+1 $&$ 2 $&$ 2x $&$ 2x+2 $&$ x $&$ 1$\\
				\hline
				$2x+2 $&$ 0 $&$ 2x+2 $&$ x+1 $&$ 2x+1 $&$ x $&$ 2 $&$ x+2 $&$ 1 $&$ 2x$\\
				\hline
			\end{tabular}
		\end{center}
		5:
		\begin{center}
			\begin{tabular}{|c|c|c|c|c|c|}
				\hline
				$+ $&$ 0 $&$ 1 $&$ 2 $&$ 3 $&$ 4 $\\
				\hline
				$0 $&$ 0 $&$ 1 $&$ 2 $&$ 3 $&$ 4$\\
				\hline
				$1 $&$ 1 $&$ 2 $&$ 3 $&$ 4 $&$ 0$\\
				\hline
				$2 $&$ 2 $&$ 3 $&$ 4 $&$ 0 $&$ 1$\\
				\hline
				$3 $&$ 3 $&$ 4 $&$ 0 $&$ 1 $&$ 2$\\
				\hline
				$4 $&$ 4 $&$ 0 $&$ 1 $&$ 2 $&$ 3$\\
				\hline
			\end{tabular}
		\end{center}
		\begin{center}
			\begin{tabular}{|c|c|c|c|c|c|}
				\hline
				$\times $&$ 0 $&$ 1 $&$ 2 $&$ 3 $&$ 4 $\\
				\hline
				$0 $&$ 0 $&$ 0 $&$ 0 $&$ 0 $&$ 0$\\
				\hline
				$1 $&$ 0 $&$ 1 $&$ 2 $&$ 3 $&$ 4$\\
				\hline
				$2 $&$ 0 $&$ 2 $&$ 4 $&$ 1 $&$ 3$\\
				\hline
				$3 $&$ 0 $&$ 3 $&$ 1 $&$ 4 $&$ 2$\\
				\hline
				$4 $&$ 0 $&$ 4 $&$ 3 $&$ 2 $&$ 1$\\
				\hline
			\end{tabular}
		\end{center}
		7:
		\begin{center}
			\begin{tabular}{|c|c|c|c|c|c|c|c|}
				\hline
				$+ $&$ 0 $&$ 1 $&$ 2 $&$ 3 $&$ 4 $&$ 5 $&$ 6$\\
				\hline
				$0 $&$ 0 $&$ 1 $&$ 2 $&$ 3 $&$ 4 $&$ 5 $&$ 6$\\
				\hline
				$1 $&$ 1 $&$ 2 $&$ 3 $&$ 4 $&$ 5 $&$ 6 $&$ 0$\\
				\hline
				$2 $&$ 2 $&$ 3 $&$ 4 $&$ 5 $&$ 6 $&$ 0 $&$ 1$\\
				\hline
				$3 $&$ 3 $&$ 4 $&$ 5 $&$ 6 $&$ 0 $&$ 1 $&$ 2$\\
				\hline
				$4 $&$ 4 $&$ 5 $&$ 6 $&$ 0 $&$ 1 $&$ 2 $&$ 3$\\
				\hline
				$5 $&$ 5 $&$ 6 $&$ 0 $&$ 1 $&$ 2 $&$ 3 $&$ 4$\\
				\hline
				$6 $&$ 6 $&$ 0 $&$ 1 $&$ 2 $&$ 3 $&$ 4 $&$ 5$\\
				\hline
			\end{tabular}
		\end{center}
		\begin{center}
			\begin{tabular}{|c|c|c|c|c|c|c|c|}
				\hline
				$\times $&$ 0 $&$ 1 $&$ 2 $&$ 3 $&$ 4 $&$ 5 $&$ 6$\\
				\hline
				$0 $&$ 0 $&$ 0 $&$ 0 $&$ 0 $&$ 0 $&$ 0 $&$ 0$\\
				\hline
				$1 $&$ 0 $&$ 1 $&$ 2 $&$ 3 $&$ 4 $&$ 5 $&$ 6$\\
				\hline
				$2 $&$ 0 $&$ 2 $&$ 4 $&$ 6 $&$ 1 $&$ 3 $&$ 5$\\
				\hline
				$3 $&$ 0 $&$ 3 $&$ 6 $&$ 2 $&$ 5 $&$ 1 $&$ 4$\\
				\hline
				$4 $&$ 0 $&$ 4 $&$ 1 $&$ 5 $&$ 2 $&$ 6 $&$ 3$\\
				\hline
				$5 $&$ 0 $&$ 5 $&$ 3 $&$ 1 $&$ 6 $&$ 4 $&$ 2$\\
				\hline
				$6 $&$ 0 $&$ 6 $&$ 5 $&$ 4 $&$ 3 $&$ 2 $&$ 1$\\
				\hline
			\end{tabular}
		\end{center}

\newpage
\section{3}
	\subsection{1 вариант}
		Приводимые в $\mathbb{F}_3$ приводимы и в $\mathbb{F}_9$.\\
		В $\mathbb{F}_3$ неприводимые это $x^2 + 1$; $x^2 + x + 2$; $x^2 + 2x + 2$\\
		В $\mathbb{F}_9$ $y^2 + 1 = 0$; $y^2 + y + 2$ имеет корень $(x + 1)$; $y^2 + 2y + 2$ имеет корень $(x + 2)$.
		
	
	\subsection{2 вариант}
		Рассмотрим элементы $F_9$. Определим, что для каждого элемента $x \in F_3$\\
		\begin{gather*}
		\sqrt{x} =
			\begin{cases}
				0 \quad \text{при} \quad x = 0 \\
				1 \quad \text{при} \quad x = 1 \\
				\overline{x} \quad \text{при} \quad x = -1
			\end{cases}
		\end{gather*}
		Заметим, что $\sqrt{x}^2 = x$.\\
		Проверим, что $y = \frac{-b + \sqrt{b^2 - 4ac} }{2a}$ является корнем $ax^2 + bx + c = 0$\\
		$\frac{(-b + \sqrt{b^2 - 4ac})^2}{4a^2} \cdot a + \frac{-b + \sqrt{b^2 - 4ac}}{2a} \cdot b + c = \frac{b^2 + b^2 - 4ac - 2\cdot b\cdot\sqrt{b^2 - 4ac} - 2\cdot b^2 + 2\cdot b\cdot\sqrt{b^2 - 4ac} + 4ac}{4a} = 0$.
		
\newpage
\section{4}
	\subsection{1 вариант}
		Покажем, что в $F_{16} = F[y]/(y^2 + y\overline{(x+1)} + 1)$ есть корни.\\
		Заметим, что если любое уравнение можно свести к $x^2 + x + c = 0$ или $x^2 + c = 0$. Докажем это: пусть уравнение вида $ax^2 + bx + c = 0$ (считаем $a$ не нулевым), тогда оно эквивалентно уравнению $x^2 + \frac{b}{a}x + \frac{c}{a}$. Сделаем замену переменных: $z \cdot \frac{b}{a} = x$. Тогда уравнение эквивалентно $z^2 + z + \frac{c \cdot a^2}{b^2} = 0$ с заменой корней (при $b \ne 0$, иначе эквивалентно уравнению вида $x^2 + c = 0$). Заметим, что $x^2 + x + c = 0$ имеют корни в $F16$: \\
		\begin{gather*}
			x^2 + x = 0 \qquad \ \ x = 0; \quad x = 1 \\
			x^2 + x + 1 = 0 \quad x = \overline{x}; \quad x = \overline{x+1}
		\end{gather*}
		Примечание: \\$(y \cdot \overline{x} + \alpha)^2 = y^2 \cdot \overline{x+1} + \alpha^2 = y \cdot \overline{x} + \overline{x+1} + \alpha^2$, поэтому решение двух оставшихся уравнений сводится к двум первым: $(y \cdot \overline{x} + \alpha)^2 + (y \cdot \overline{x} + \alpha) + c = \alpha^2 + \alpha + \overline{x+1} + c$\\
		\begin{gather*}
		x^2 + x + \overline{x} = 0 \qquad \ \ x = y \cdot \overline{x} + \overline{x}; \quad x = y \cdot \overline{x} + \overline{x+1} \\
		x^2 + x + \overline{x+1} = 0 \quad x = y \cdot \overline{x}; \qquad \ \ x = y \cdot \overline{x} + 1 
		\end{gather*}
		Покажем, что у уравнений вида $x^2 + c = 0$ есть решения: \\
		$0 \cdot 0 = 0$, откуда $x^2 + 0 = 0$ имеет корень. \\
		$1 \cdot 1 = 1$, откуда $x^2 + 1 = 0$ имеет корень. \\
		$\overline{x} \cdot \overline{x} = \overline{x+1}$, откуда $x^2 + \overline{x+1} = 0$ имеет корень. \\
		$\overline{x+1} \cdot \overline{x+1} = \overline{x}$, откуда $x^2 + \overline{x} = 0$ имеет корень. 
		
	\subsection{2 вариант}
	$\mathbb{Z}_4 = \mathbb{Z}_2[x]/(x2 + x + 1)$
	\begin{gather*}
		\begin{matrix}
			y^2,\ 0 & y^2 + y,\ 0 & y^2 + yx,\ 0 & y^2 + y(x + 1),\ x + 1 \\
			y^2 + 1,\ 1 & y^2 + y + 1,\ x & y^2 + yx + 1,\ \varnothing & y^2 + y(x + 1) + 1,\ \varnothing \\
			y^2 + x,\ x + 1 & y^2 + y + x,\ \varnothing & y^2 + yx + x,\ \varnothing & y^2 + y(x + 1) + x,\ 1\\
			y^2 + x + 1,\ x & y^2 + y + x + 1,\ \varnothing & y^2 + yx + x + 1,\ \varnothing & y^2 + y(x + 1) + x + 1,\  \varnothing
		\end{matrix}
		\\
		(\mathbb{Z}_2[x]/(x2 + x + 1))[y]/(y2 + y + x)\\
		z^2 + z + x + 1, z = y + x \Rightarrow = (y + x)^2 + (y + x) + x + 1 = \\ = y^2 + x^2 + y + x + x + 1 = y + x + x + 1 + y + x + x + 1 = 0
		\\ \\
		z^2 + zx + 1, z = xy \Rightarrow = x^2y^2 + x^2y + 1 = (x + 1)(x + y) + (x + 1)y + 1 = \\ = x^2 + xy + x + y + xy + y + 1 = x + 1 + xy + x + y + xy + y + 1 = 0
		\\ \\
		z^2 + zx + x, z = yx + 1 \Rightarrow = (yx + 1)^2 + (yx + 1)x + x = \\ = y^2x^2 + 1^2 + x(yx + 1 + 1) = y^2x^2 + 1 + yx^2 = x^2(y^2 + y) + 1 = (x + 1)x + 1 = 0
		\\ \\
		z^2 + z(x + 1) + 1, z = y(x + 1) + 1 \Rightarrow = (y(x + 1) + 1)^2 + y(x + 1)^2 + (x + 1) + 1 = \\ = (y + x)x + 1 + yx + x = yx + x + 1 + 1 + yx + 1 = 0
		\\ \\
		z^2+z(x+1)+x+1, z = y(x+1) \Rightarrow = x(y+x)+yx+x+1 = yx+x+1+yx+x+1 = 0
	\end{gather*}
		
\newpage	
\section{5}
	\subsection{1 вариант}
		Рассмотрим группу обратимых для $n = 12 \quad \mathbb{Z}/ 12 \mathbb{Z}$, это $\{ 1,\ 5,\ 7,\ 11 \}$.\\
		Заметим, что $5 \cdot 5 = 25 = 1,\quad 7 \cdot 7 = 49 = 1,\quad 11 \cdot 11 = -1 \cdot -1 = 1$, откуда следует, что эта группа не циклична.
		
	\subsection{2 вариант}
		Рассмотрим группу обратимых для $n = 8 \quad \mathbb{Z}/ 8 \mathbb{Z}$, это $\{ 1,\ 3,\ 5,\ 7 \}$.\\
		Заметим, что $3 \cdot 3 = 9 = 1,\quad 5 \cdot 5 = 25 = 1,\quad 7 \cdot 7 = -1 \cdot -1 = 1$, откуда следует, что эта группа не циклична.
		
\newpage		
\section{6}
	\subsection{1 вариант}
		Докажем, что существует первообразный корень в $Z/pZ$.\\
		\textbf{(1) Т.Ферма}: $\alpha^{p-1} = 1$ при $\alpha \ne 0$. Доказательство:\\
		Рассмотрим всевозможные произведения $\alpha$ на другие элемента поля. Так как это поле, значит в нём нет делителей $0$, откуда не может быть такого, что $\alpha*x = \alpha * y$ при $x \ne y$, поэтому всевозможные произведения различны. Откуда следует, что $\alpha \dot 2\alpha \dot ... \dot (p-1)\alpha = (p-1)!  <=>  a^{p-1}(p-1)! = (p-1)!  <=> a^{p-1} = 1$ $((p-1)! \ne 0)$.\\ \\
		\textbf{(2) Лемма}: $n = \sum \phi (i)$, где $i$ пробегает по всем делителям $n$ (Здесь мы работаем в натуральных числах).\\
		Доказательство:\\
		Будем говорить, что $\alpha \in [1,n]$ принадлежит множеству $M_i$ (где $i$ -- делитель $n$), если $\frac{\alpha}{\frac{n}{i}}$ целое, меньше $i$ и взаимнопросто с $i$. Нетрудно видеть, что каждое $\alpha$ может принадлежать не более $1$ множеству, так как то, что $\alpha \in M_{i_1} \ \Leftrightarrow \ (\alpha,\ n) = \frac{n}{i_1}$. Также видно, что любое $\alpha$ принадлежит хоть какому то множеству.\\ 
		Теперь заметим, что в каждом множестве $M_i$ ровно $\phi(i)$ элементов, так как таких $\alpha:\ \frac{\alpha}{n/i} \in Z$ - $i$ $(\frac{n}{i}, \frac{2n}{i},\ ... \: , \frac{in}{i})$, при этом среди чисел в промежутке $[1,i]$ взаимнопростых $\phi(i)$. Откуда следует то, что и требовалось доказать.\\ \\
		\textbf{(3)} Заметим, что элементов порядка $k$ либо $0$, либо $\phi(k)$. Доказательство:\\
		Предположим есть хотя бы $1$. (элемент $g$) Тогда элементы вида $g,\ g^2,\ g^3,\ ... ,\ g^k$ различны и являются корнями уравнения $x^k - 1 = 0$, откуда следует, что других корней нет, при этом если $\alpha \in [1,k]$ не взаимнопросто с $k$ (пусть $(\alpha,k) = y$), то порядок у $g^{\alpha} = \frac{k}{y}$, что не равно k. Поэтому элементов порядка $k$ ровно $\phi(k)$.\\
		\\
		Следствие \textbf{(1)}, \textbf{(2)} и \textbf{(3)}:\\
		Заметим, что если $k$ - не делитель $p-1$, то чисел порядка $k$ - 0, так как порядок больше чем $p-1$ быть не может (так как иначе среди чисел $g,\ g^2,\ ...,\ g^i$ найдутся $2$ одинаковых, и тогда разделим одно на другое и получим, что порядок меньше, чем предполагался, откуда следует противоречие), при этом любое число в степени $p-1 = 1$. Теперь рассмотрим все $k$, которые делят $p-1$. Заметим, что для всякого $k$ количество чисел порядка $k$ не больше чем $\phi(k)$, при этом сумма всех $\phi(i)$, где $i$ делит $p-1$, равна $p-1$, и всякое ненулевой элемент принадлежит хоть какому то порядку, откуда следует, что для всякого k количество чисел порядка k ровно $\phi(k)$, откуда есть элементы порядка $p-1$, что и требовалось доказать.\\
		\\ \\
		Пусть это $g$, и $g^{p-1} = 1 + pk$. Рассмотрим числа вида $(g + pt)^{p-1} \quad \forall t \in Z$. Тогда $(g + pt)^{p-1} = 1 + p \cdot (k + (p-1)g^{p-2} \cdot t + p \cdot X)$. Заметим, что существует такое $t_1$, что $k + (p-1)g^{p-2} \cdot t_1 + p \cdot X = 1$ ($\mod \quad \mathbb{Z}/p^{n-1} \mathbb{Z}$), так как существует обратное у $(p-1) \cdot g^{p-2}$ (назовем его $t_0$). Рассмотрим $t_1 = t_0 \cdot (1 - k - p \cdot X)$, заметим, что $1+p$ принадлежит показателю вида $p^\alpha$, так как $g + pt_1$ принадлежит показателю вида $p^\beta \cdot (p-1)$, так как все возможные непустые показатели являются делителями $p^{n-1} \cdot (p-1)$, при этом $(g + pt_1)^{p-1} \ne 1$. \\ \\
		Рассмотрим $(1+p) ^{p^{\alpha}} = 1 + p^{\alpha + 1} \cdot (1 + p \cdot Y) = 1 + p^{\alpha + 1} \cdot u_{\alpha}$, где $u_{\alpha}$ взаимнопросто с $p$. Предположим, что $(1+p) ^{p^{\alpha}} = 1$, тогда $p^{\alpha + 1} = 0$, откуда $\alpha + 1 = n$, поэтому $1 + p$ принадлежит показателю $p^{n-1}$, следовательно $g + pt_1$ принадлежит показателю $p^{n-1} \cdot (p-1)$, и тогда $g + pt_1$ -- первообразный корень.\\
		\\
	\subsection{2 вариант}
		\textbf{Лемма 1}\\
		Пусть $G$ -- конечная абелева группа и $a$ -- элемент наибольшего порядка в ней. Тогда порядок любого элемента группы $G$ делит порядок $a$.\\
		\\
		\textbf{Доказательство}\\ 
		$x^{ord(x)} = 1$ Пусть $x$ -- произвольный элемент из $G$. Если $ord(x)$ не делит $ord(a)$, то существует такое простое $q^\alpha$ и показатель  $\alpha \geq 1$, что $q$ делит $ord(x)$ и не делит $ord(a)$. Пусть $\beta \geq 0$ -- наибольшее число такое, что $q^\beta$ делит $ord(a)$, тогда $\alpha > \beta$.\\
		Положим $y = x^{ord(x) / q^\alpha} = q$ и $b = a^{q^{\beta}}$. Тогда $ord(y) = q^\alpha$ и $ord(b) = ord(a) = q / q^\beta$. Так как $ord(y)$ и $ord(b)$ взаимно просты и группа $G$ абелева, то $ord(yb) = ord(y) \cdot ord(b) = ord(a)q^{\alpha - \beta} > ord(a)$ -- противоречие.\\
		\\
		По \textbf{Th Лагранжа}\\ порядок подгруппы конечной группы делит порядок этой группы.\\ 
		\textbf{Следствие}\\ Порядок элемемнта конечной группы делит порядок этой группы.\\
		\\
		\textbf{Докажем Теорему}:\\ 
		Мультипликативная группа конечного поля является циклической.\\
		\\
		\textbf{Доказательство}:\\ 
		Пусть $\mathbb{K}$ -- конечное поле. Докажем, что $\mathbb{K} = \mathbb{K} \text{(без нуля)}$ -- циклическая. Пусть $x_1,\ x_2,\ ... \: ,\ x_n$ -- все элементы группы $\mathbb{K}^{\star}$ и пусть $x_1$ -- элемент наибольшего порядка $d$ в ней. По Лемме 1 порядки всех элементов $x_i$ делят $d$, в частности, все $x_i$ удовлетворяют уравнению $x^d - 1 = 0$ в $\mathbb{K}$. Знаем, что корней уравнения не больше $d$ $\Rightarrow$ $d \geq n$. Однако по следствию из Лагранжа $d \bigm| n \quad \Rightarrow \quad n = d$ значит $x_1$ порождает $\mathbb{K}^{\star}$.\\
		\\
		\textbf{Следствие}:\\ 
		Если $p$ -- простое, то $Z_p$ -- циклическая группа порядка $p - 1$.\\
		\\
		\textbf{Предположение}:\\
		Если $p > 2$ -- простое, то группа $Z^{\star}_{p^n}$ циклическая для всех $n > 0$.\\
		\\
		\textbf{Доказательство}:\\
		По следствию существует существует такое натуральное число $g$, что $g^{p - 1} \equiv 1 \ (\mod p)$. Если $g^{p-1} \equiv 1 \ (\mod p^2)$, то $(g + p)^{p-1} = g^{p - 1} + (p - 1)g^{p - 2} + p^2(...) = 1 + (p - 1)g^{p - 2}p \equiv \overline{1} \ (\mod p^2)$. Поэтому можно считать что $g^{p - 1} \not\equiv 1 \ (\mod p^2)$ Таким образом $g^{p - 1} = 1 + p \cdot u$, где $u$ не делится на $p$.\\
		\\
		Докажем, что вычет $g$ порождает $Z^{\star}_{p^n}$\\
		Докажем, что $g^{(p-1)p^k} = 1 + p^{k+1}u_k$ по индукции, база была доказана ранее.\\
		Шаг: $g^{(p-1)p^{k+1}} = (1 + p^{k+1}u_k)^p = 1 + p \cdot p^{k+1}u_k + \sum^p_{i = 2} {p \choose i} (p^{k+1}u_k)^i$\\
		$\sum^p_{i = 2} {p \choose i} (p^{k+1}u_k)^i$ делится на $p^{k+3}$, а $ p \cdot p^{k+1}u_k$ на $p^{k+2} \quad \Rightarrow \quad \frac{\sum^p_{i = 2} {p \choose i} (p^{k+1}u_k)^i}{p^{k+2}} + u_k$ не делится на $p$, так как $\frac{\sum^p_{i = 2} {p \choose i} (p^{k+1}u_k)^i}{p^{k+2}}$ делится на $p$, а $u_k$ нет, что и требовалось доказать\\
		$\Rightarrow$ $g$ порождает $Z^{\star}_{p^n}$\\
		\\
		\textbf{Лемма 2}\\
		$\forall n \in \mathbb{N} \ \exists ! v$ не делящееся на $p:\ (p + 1)^{p^{n - 1}} = v \cdot p^n + 1$\\
		База:\\
		$n = 1 \quad \Rightarrow \quad v = 1$\\
		$(p + 1)^{p^n} = (v \cdot p^n + 1)^p = \sum^p_{i = 0} {p \choose i} (v^i p^{ni}) = 1 + pvp^n + \sum^p_{i = 2} {p \choose i} (v^i p^{ni}),\ pvp^n + \sum^p_{i = 2} {p \choose i} (v^i p^{ni})$ делится на $p^{n+1}$, что и требовалось доказать\\
		\\
		Докажем, что $ord(p + 1) \geq p^{n - 1}$. Пусть нет, тогда $ord(p + 1) < d = p^{n - 1}$ $d \bigm| p^{n - 1} \quad d = p^k,\ k < n - 1$, тогда $(p + 1)^{p^k} = v \cdot p^n + 1$, но по лемме 2, $\exists! u \: : \: (p + 1)^{p^k} = up^{k + 1} + 1 \quad \Rightarrow \quad k = n - 1$. Противоречие. $\Rightarrow \quad d \geq p^{n - 1}$\\
		\\
		Докажем, что $d = p^{n - 1}$\\
		Пусть $(p + 1)^{p^{n-1}} \equiv 1 \quad (\mod p^n)$\\
		Докажем $(p + 1)^{p^{n}} \equiv 1 \quad (\mod p^{n+1})$\\
		$(p + 1)^{p \cdot p^{n - 1}} = ((p + 1)^{p^{n - 1}})^p = (1 + lp^n)^p = 1 + \sum^p_{i = 1} {p \choose i} (lp^n)^i \equiv 1 (\mod p^{n+1})$, что и требовалось доказать\\
	
	