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-16.tex | 109 --------------------------------------------------------------
 1 file changed, 109 deletions(-)
 delete mode 100644 dm-16.tex

(limited to 'dm-16.tex')

diff --git a/dm-16.tex b/dm-16.tex
deleted file mode 100644
index 054f0a2..0000000
--- a/dm-16.tex
+++ /dev/null
@@ -1,109 +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} дм-16 (\texttt{cw16\_plus})}
-\title{Дискретная математика 16}
-\author{Шарафатдинов Камиль БПМИ192}
-\date{билд: \today}
-
-% -- Here bet  dragons --
-\begin{document}
-
-\maketitle
-
-\twocolumn
-
-\dmquestion{1}
-
-    $\varphi(n) < n$, поэтому в $n!$ точно есть множитель $\varphi(n)$.
-
-    Пусть $n! = \varphi(n) \cdot Q$
-
-    Тогда по теореме Эйлера (так как $(n, 2) = 1$)
-    \[
-        2^{n!} = 2^{\varphi(n) \cdot Q} = \br{ 2^{\varphi(n)} }^Q = 1^Q = 1 \pmod{n}
-    \]
-
-    Поэтому $2^{n!} - 1 \divby n$
-
-\dmquestion{2}
-
-    Посмотрим, какие остатки может иметь $a^{10}$ при делении на $11$:
-    Либо $a$ делится на $11$, тогда $a^{10} = a = 0 \pmod{11}$. Либо $a$ не делится на $11$ и тогда, так как $11$ - простое число, $a^{10} = 1 \pmod{11}$ по МТФ. Аналогично для других букв. Тогда сумма
-    \[
-        a^{10} + b^{10} + c^{10} + d^{10} + e^{10} + f^{10}
-    \]
-    по модулю $11$ может принимать любое значение от $0$ до $6$. Но по условию она равна $0$, поэтому и каждое слагаемое равно $0$ по модулю $11$.
-    Тогда каждая переменная делится на $11$ и $abcdef$ делится на $11^6$ \qed
-
-\dmquestion{3}
-    \[
-        7^2 = 49 = 1 \pmod{16}
-    \]
-    Поэтому $7^{7^7} = 7 \pmod{16}$, так как $7^7$ - нечетное число.
-    Тогда по теореме Эйлера
-    \[
-        7^{7^{7^7}} = 7^7 \pmod{17}
-    \]
-    \[
-        7^7 = 49^3 \cdot 7 = (-2)^3 \cdot 7 = -8 \cdot 7 = 12 \pmod{17}
-    \]
-
-\dmquestion{4}
-    \begin{align*}
-        x^2 = 1 \pmod{200}\\
-        x^2 - 1 = 0 \pmod{200}\\
-        (x + 1)(x - 1) = 0 \pmod{200}
-    \end{align*}
-
-    Если $x$ - нечетный, то такое произведение всегда делится на $8$,
-    а если четный, то не делится даже на $2$.
-
-    Если одна из скобок делится на $5$, то другая точно не делится.
-
-    Поэтому нам нужно решить такую систему:
-    \[
-        \begin{cases}
-            x = 1 \pmod{2}\\
-            \begin{sqcases}
-                x + 1 = 0 \pmod{25}\\
-                x - 1 = 0 \pmod{25}
-            \end{sqcases}
-        \end{cases}
-    \]
-    Решениями являются вычеты $\{49, 51, 99, 101, 149, 151, 199, 1\}$
-
-\dmquestion{5}
-    Число заканчивается на $0001$ тогда и только тогда, когда оно сравнимо с $1$ по модулю $10^4$.
-    По теореме Эйлера
-    \[
-        3^{\varphi(10000)} = 1 \pmod{10000}
-    \]
-
-\dmquestion{6}
-    \begin{align*}
-        x^2 = x \pmod{10^k}\\
-        x(x - 1) = 0 \pmod{10^k}
-    \end{align*}
-
-    Если $x$ делится на $2^n$, то $x - 1$ на $2$ не делится.
-    Поэтому, на $2^k$ делится либо $x$, либо $x - 1$. Аналогично с $5$.
-    Тогда есть 4 случая:
-    \begin{enumerate}
-        \item $x \divby 10^k \Rightarrow x = 0 \pmod{10^k}$
-        \item $x - 1 \divby 10^k \Rightarrow x = 1 \pmod{10^k}$
-        \item $x \divby 2^k, \quad x - 1 \divby 5^k$
-        \item $x \divby 5^k, \quad x - 1 \divby 2^k$
-    \end{enumerate}
-
-    В каждом из 3 и 4 пунктов есть ровно одно решение по модулю $10^k$ по китайской теореме об остатках. Решения не совпадают, потому что иначе $x$ и $x - 1$ должны бы были одновременно делиться на $2^k$. По тем же соображениям они не пересекаются и с пунктами 1 и 2.
-    \qed
-
-\end{document}
-- 
cgit v1.2.1-18-gbd029

