From f642380d55c66e4e5deaaa6c7cef15f6dbfe36c6 Mon Sep 17 00:00:00 2001
From: syn <isaqtm@gmail.com>
Date: Wed, 15 Apr 2020 04:35:30 +0300
Subject: Reorganize & alg-1

---
 dm-15.tex | 146 --------------------------------------------------------------
 1 file changed, 146 deletions(-)
 delete mode 100644 dm-15.tex

(limited to 'dm-15.tex')

diff --git a/dm-15.tex b/dm-15.tex
deleted file mode 100644
index db0de91..0000000
--- a/dm-15.tex
+++ /dev/null
@@ -1,146 +0,0 @@
-\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}
-- 
cgit v1.2.1-18-gbd029

