1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
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}
|
