\documentclass[a4paper,oneside]{article}

\usepackage[utf8]{inputenc}
\usepackage[T2A]{fontenc}
\usepackage[english,russian]{babel}

\usepackage{amsmath}
\usepackage{mathtools}
\usepackage{amsfonts}
\usepackage{enumitem}
\usepackage{amsthm}
\usepackage{minted}
\setminted{fontsize=\small, breaklines=true, style=emacs, linenos}
\usepackage{graphicx}
\graphicspath{ {./images/} }
\usepackage{float}

\newtheorem{theorem}{Теорема}
\newtheorem*{theorem*}{Теорема}

% --- Определение --- %
\theoremstyle{definition}
\newtheorem{definition}{Определение}
\newtheorem*{definition*}{Определение}
% ------------------- %

\theoremstyle{definition}
\newtheorem*{example}{Пример}


\title{{Криптографические методы защиты информации}\\{Лабораторная работа №6}}
\author{Гущин Андрей, 431 группа, 1 подгруппа, 2 вариант}
\date{\the\year{} г.}

\begin{document}

\maketitle

\begin{definition}
  \textbf{Группа} --- непустое множество, на котором определена ассоциативная
  бинарная операция, причём для этой операции имеется нейтральный элемент, и
  каждый элемент множества имеет обратный.
\end{definition}

\begin{definition}
  \textbf{Циклическая группа} --- группа $(G, \cdot)$, которая может быть
  порождена одним элементом $a$, то есть все её элементы являются степенями
  $a$. Обозначается как $G = \langle a \rangle$.
\end{definition}

\begin{definition}
  \textbf{Подгруппа} --- подмножество $H$ группы $G$, которое является группой
  относительно операции, определённой в $G$.
\end{definition}

\begin{theorem}
  \label{thm:all_cycle}
  Каждая подгруппа циклической группы является циклической.
\end{theorem}
\begin{proof}
  Допустим, $G = \langle g \rangle = \{ g^k : k \in \mathbb{Z} \}$ ---
  циклическая группа. Пусть $H$ --- подгруппа $G$. Если $H = \{ 1 \}$, то
  $H$ --- циклическая. Положим, что $H$ --- нетривиальная подгруппа и пусть
  $g^k \in H$, где $g^k \neq 1$. Тогда, так как $H$ является подгруппой,
  $g^{-k} = (g^k)^{-1} \in H$. Получаем, что $H$ содержит положительную
  степень числа $g$, отличную от 1. Возьмём минимальное положительное $m$
  такое, что $g^m \in H$. Очевидно, что все степени $g^m$ также принадлежат
  $H$, то есть $\langle g^m \rangle \subseteq H$.

  Докажем, что это выражение является равенством. Пусть $g^k$ является
  любым элементом $H$. Мы можем выразить $k = qm + r$, где $0 \leq r < m$.
  Но $g^k = g^{qm + r} = g^{qm} g^r = (g^m)^q g^r$. Получаем
  \begin{equation*}
    g^r = (g^m)^{-q} g^k \in H
  \end{equation*}

  Так как $m$ --- минимальное положительное целое число такое, что $g^m \in
  H$ и при этом $0 \leq r < m$, следует, что $r = 0$. Тогда,
  $g^k = (g^m)^q \in \langle g^m \rangle$. Таким образом, мы показали, что
  $H \subseteq \langle g^m \rangle \implies H = \langle g^m \rangle$.

  Получаем, что $H$ --- цикличная с порождающим элементом $g^m$, где $m$ ---
  минимальное положительное целое число, для которого справедливо $g^m \in H$.
\end{proof}

\begin{theorem}[Фундаментальная теорема конечных цикличных групп]
  Пусть $G = \langle g \rangle$ --- цикличная группа порядка $n$. Тогда,
  \begin{enumerate}
    \item
      Если $H$ --- подгруппа $G$, то $H = \langle g^d \rangle$ для
      некоторого $d \mid n$.
    \item Если $H$ --- подгруппа $G$ и $|H| = k$, то $k \mid n$.
    \item
      Если $k \mid n$, то $\langle g^{n/k} \rangle$ --- единственная
      подгруппа $G$ порядка $k$.
  \end{enumerate}
\end{theorem}
\begin{proof}
  \begin{enumerate}
    \item \label{thm:fund_1}
      По Теореме \ref{thm:all_cycle}, $H$ --- циклическая группа.
      Так как $|G| = n < \infty \implies H = \langle g^m \rangle$, где
      $m > 0$. Пусть $d = \gcd(m, n)$. Так как $d \mid n$, достаточно
      показать, что $H = \langle g^d \rangle$. Но $d \mid m$, поэтому
      $m = qd$. Тогда $g^m = (g^d)^q \implies g^m \in \langle g^d \rangle$.
      Таким образом, $H = \langle g^m \rangle \subseteq \langle g^d \rangle$.
      Но $d = rm + sn$, где $r, s \in \mathbb{Z}$, поэтому
      \begin{equation*}
        g^d = g^{rm + sn} = g^{rm} g^{sn} = (g^m)^r (g^n)^s =
        (g^m)^r (1)^s = (g^m)^r \in \langle g^m \rangle = H
      \end{equation*}

      Получаем, что $\langle g^d \rangle \subseteq H \implies
      \langle g^d \rangle = H$.
    \item
      В следствие пункта \ref{thm:fund_1}, $H = \langle g^d \rangle$,
      где $d \mid n$. Тогда $k = |H| = n / d$. Получаем, что $k \mid n$.
    \item
      Допустим $K$ --- подгруппа $G$ порядка $k$. По пункту \ref{thm:fund_1},
      пусть $K = \langle g^m \rangle$, где $m \mid n$. $k = |K| = |g^m|
      = n/m$. Получаем $m = n/k \implies K = \langle g^{n/k} \rangle$.
  \end{enumerate}
\end{proof}

\begin{example}
  Пусть $G = \mathbb{Z}_6 = \{ 0, 1, 2, 3, 4, 5 \}$ --- кольцо вычетов по
  модулю 6. Вычислим все подгруппы, беря каждый из элементов как порождающий.
  \begin{align*}
    H_0 &= \{ 0 \} \\
    H_1 &= \{ 0, 1, 2, 3, 4, 5 \} = G \\
    H_2 &= \{ 0, 2, 4 \} \\
    H_3 &= \{ 0, 3 \} \\
    H_4 &= \{ 0, 2, 4 \} = H_2 \\
    H_5 &= \{ 0, 1, 2, 3, 4, 5 \} = H_1 = G
  \end{align*}

  Делителями числа 6 являются $\{ 1, 2, 3, 6 \}$. Можно заметить, что для
  каждого из делителей существует единственная уникальная подгруппа
  соответствующего порядка (для 1 --- $\langle 0 \rangle$, для 2 ---
  $\langle 3 \rangle$, для 3 --- $\langle 2 \rangle$, для 6 --- $G$).
\end{example}

\end{document}