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
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
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}
|
