1 files changed, 146 insertions, 0 deletions
diff --git a/dm/dm-15.tex b/dm/dm-15.tex
new file mode 100644
index 0000000..db0de91
--- /dev/null
+++ b/dm/dm-15.tex
@@ -0,0 +1,146 @@
+\documentclass[11pt]{article}
+\usepackage[x11names, svgnames, rgb]{xcolor}
+%\usepackage{tikz}
+%\usetikzlibrary{arrows,shapes}
+
+\usepackage{scrextend}
+
+\input{intro}
+
+\lhead{\color{gray} Шарафатдинов Камиль 192}
+\rhead{\color{gray} дм-15 (\texttt{cw15\_plus})}
+\title{Дискретная математика 15}
+\author{Шарафатдинов Камиль БПМИ192}
+\date{билд: \today}
+
+% -- Here bet  dragons --
+\begin{document}
+
+\maketitle
+
+\twocolumn
+
+\dmquestion{1}
+    \[
+        99^{1000} = (-1)^{1000} = 1 \pmod{100}
+    \]
+
+\dmquestion{2}
+    \begin{align*}
+        x + 10y &=\\
+        &= x + 10y - 13x - 13y\\
+        &= -12x - 3y\\
+        &= -3(4x + y) \pmod{13}
+    \end{align*}
+
+    Так как $(3; 13) = 1$, то $x + 10y = 0 \pmod{13}$ тогда и только тогда,
+    когда $4x + y = 0 \pmod{13}$
+
+\dmquestion{3}
+    \begin{align*}
+        53x &= 1 &\pmod{42}\\
+        11x &= 1 + 42 \cdot 6 &\pmod{42}\\
+        11x &= 253 &\pmod{42}\\
+        x &= 23 &\pmod{42}
+    \end{align*}
+
+\dmquestion{4}
+    \begin{align*}
+        74x + 47y = 2900\\
+        27x = 2900  \pmod{47}\\
+        27x = 33    \pmod{47}\\
+        9x = 11     \pmod{47}\\
+        9x = -36    \pmod{47}\\
+        x = -4 = 43 \pmod{47}\\\\
+        74 \cdot 43 + 47y = 2900\\
+        47y = -282\\
+        y = -6
+    \end{align*}
+
+    Все решения имеют вид
+    \[
+        (x_0 + 47k; y_0 - 74k), \qquad k \in \mathbb{Z}
+    \]
+
+    Поэтому неотрицательных решений у этого уравнения нет
+
+\dmquestion{5}
+    \[
+        \frac{n^2 - n + 1}{n^2 + 1}
+    \]
+    
+    Предположим противное: пусть такая дробь сократима.
+    
+    Пусть существует $p > 1$ такое, что
+    \[
+        p \mid (n^2 + 1), p \mid (n^2 - n + 1)
+    \]
+    
+    Значит,
+    \[
+        n = (n^2 + 1) - (n^2 - n + 1) \text{ тоже делится на $p$.}
+    \]
+    
+    Значит, $p \mid n^2$.
+
+    Но $n^2 + 1 = 1 \pmod{p}$. Противоречие.
+
+\dmquestion{6}
+
+    \textbf{Лемма}
+    \[
+        3^m - 1 = 3^{m - n} - 1 \pmod{3^n - 1}
+    \]
+    
+    Доказательство:
+    \begin{align*}
+        3^{m - n}(3^n - 1) = 0 \pmod{3^n - 1}\\
+        3^m - 3^{m - n} = 0 \pmod{3^n - 1}\\
+        3^m = 3^{m - n} \pmod{3^n - 1}\\
+        3^m - 1 = 3^{m - n} - 1 \pmod{3^n - 1}\\
+        \qed
+    \end{align*}
+
+    По алгоритму Евклида и лемме (просто вычитаем одну степень из другой):
+    \begin{align*}
+        (3^{133} - 1, 3^{101} - 1) =\\
+        (3^{101} - 1, 3^{32} - 1) =\\
+        (3^{32} - 1, 3^5 - 1) =\\
+        (3^2 - 1, 3^5 - 1) =\\
+        (3^1 - 1, 3^2 - 1) =\\
+        (2, 8) = 2
+    \end{align*}
+
+\dmquestion{7}
+
+    \[
+        \frac{1}{1} + \frac{1}{2} + \ldots + \frac{1}{p - 1} =
+        \frac{\frac{(p - 1)!}{1} + \frac{(p - 1)!}{2} + \ldots + \frac{(p - 1)!}{p - 1}}{(p - 1)!}
+    \]
+
+    Сгруппируем слагаемые в числителе так, чтобы их знаменатели в сумме равнялись $p$.
+    Так можно сделать, потому что их четное число.
+    \[
+        \frac{
+            \br{ \frac{(p - 1)!}{1} + \frac{(p - 1)!}{p - 1} } +
+            \br{ \frac{(p - 1)!}{2} + \frac{(p - 1)!}{p - 2} } + \ldots
+        }{(p - 1)!}
+    \]
+
+    Заметим, что каждая скобка тогда делится на $p$:
+    \begin{gather*}
+        \frac{(p - 1)!}{k} + \frac{(p - 1)!}{p - k} =\\[8pt]
+        (p - 1)! \br{ \frac{(p - k) + k}{k(p - k)}} =\\[8pt]
+        p\frac{(p - 1)!}{k(p - k)}
+    \end{gather*}
+
+    Так как это сумма факториалов, деленных на одно число, меньшее аргумента факториала, то это все еще целое число, а так как $p$ - простое и точно не делится на $k$ и $p - k$, то его можно вынести за скобку.
+
+    Тогда наша сумма представляется в виде
+
+    \[
+        \frac{p \cdot Q}{(p - 1)!}
+    \]
+
+    Так как в факториале нет множителей, делящих $p$, то $p$ останется в числителе, значит, числитель делится на $p$ \qed
+\end{document}