1 files changed, 90 insertions, 0 deletions
diff --git a/report/lab1/lab1.tex b/report/lab1/lab1.tex
new file mode 100644
index 0000000..4b26359
--- /dev/null
+++ b/report/lab1/lab1.tex
@@ -0,0 +1,90 @@
+\documentclass[a4paper,oneside]{article}
+
+\usepackage[utf8]{inputenc}
+\usepackage[T2A]{fontenc}
+\usepackage[english,russian]{babel}
+
+\usepackage{amsmath}
+\usepackage{indentfirst}
+\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}{Теорема}[subsection]
+\newtheorem*{theorem*}{Теорема}
+
+% --- Определение --- %
+\theoremstyle{definition}
+\newtheorem{definition}{Определение}[subsection]
+\newtheorem*{definition*}{Определение}
+% ------------------- %
+
+\title{{Алгоритмы алгебры и теории чисел}\\{Лабораторная работа №1}}
+\author{Гущин Андрей, 431 группа, 1 подгруппа}
+\date{\the\year{} г.}
+
+\begin{document}
+
+\maketitle
+
+\section{Задача}
+
+Решите сравнение вида $ax \equiv b \pmod{m}$ с помощью алгоритма Евклида.
+
+\section{Алгоритм}
+
+Алгоритм Евклида, вычисляющий наибольший общий делитель двух чисел, можно расширить
+для нахождения по заданным числам $a$ и $b$ таких целых $x$ и $y$, что
+$ax + by = d$, где $d$ --- $\gcd(a, b)$.
+
+Пусть для положительных целых чисел $a$ и $b$ $(a > b)$ известны $d = \gcd(a, b)
+= \gcd(b, a \pmod{b})$, а также числа $x'$ и $y'$, для которых $d = x'b + y'(a
+\pmod{b})$. Тогда значения $x$ и $y$, являющиеся решениями уравнения $ax + by =
+d$, находятся из соотношений
+\begin{equation*}
+    x = y', y = x' - y' \frac{a}{b}
+\end{equation*}
+
+Линейным сравнением называется уравнение вида $ax \equiv b \pmod{m}$. Оно имеет
+решение тогда и только тогда, когда $b$ делится на $d = \gcd(a, m)$. Если $d >
+1$, то уравнение можно упростить, заменив его на $a'x \equiv b' \pmod{m'}$),
+где $a' = a / d$, $b' = b / d$, $m' = m / d$. После такого преобразования числа
+$a'$ и $m'$ являются взаимно простыми.
+
+Алгоритм решения уравнения $a'x \equiv b' \pmod{m'}$) со взаимно простыми $a'$ и
+$m'$ состоит из двух частей:
+\begin{enumerate}
+  \item
+    Решаем уравнение $a'x = 1 \pmod{m'}$). Для этого при помощи расширенного
+    алгоритма Евклида ищем решение $(x_0, y_0)$ уравнения $a'x + m'y = 1$. Взяв
+    по модулю $m'$ последнее равенство, получим $a'x_0 = 1 \pmod{m'}$).
+  \item
+    Умножим на $b'$ равенство $a'x_0 = 1 \pmod{m'}$). Получим $a'(b'x_0) = b'
+    \pmod{m'}$), откуда решением исходного уравнения $a'x = b' \pmod{m'}$) будет
+    $x = b'x_0 \pmod{m'}$).
+\end{enumerate}
+
+Все решения сравнения находят по формуле $x_i = x + m'i$, где $i = 0, \dots, d -
+1$.
+
+\section{Реализация}
+
+Для реализации программы использовался язык программирования Rust с системой
+сборки cargo.
+
+\inputminted{rust}{../../lab1/src/main.rs}
+
+\section{Тестирование}
+
+\begin{figure}[H]
+    \centering
+    \includegraphics[width=\textwidth]{test.png}
+\end{figure}
+
+\end{document}