1 files changed, 109 insertions, 0 deletions
diff --git a/dm/dm-16.tex b/dm/dm-16.tex
new file mode 100644
index 0000000..054f0a2
--- /dev/null
+++ b/dm/dm-16.tex
@@ -0,0 +1,109 @@
+\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}