StepanovRose.lyx

#LyX 2.3 created this file. For more info see http://www.lyx.org/
\lyxformat 544
\begin_document
\begin_header
\save_transient_properties true
\origin unavailable
\textclass extreport
\use_default_options true
\begin_modules
theorems-ams-bytype
theorems-chap-bytype
\end_modules
\maintain_unincluded_children false
\language russian
\language_package default
\inputencoding auto
\fontencoding global
\font_roman "default" "default"
\font_sans "default" "default"
\font_typewriter "default" "default"
\font_math "auto" "auto"
\font_default_family default
\use_non_tex_fonts false
\font_sc false
\font_osf false
\font_sf_scale 100 100
\font_tt_scale 100 100
\use_microtype false
\use_dash_ligatures true
\graphics default
\default_output_format default
\output_sync 0
\bibtex_command default
\index_command default
\paperfontsize default
\spacing single
\use_hyperref false
\papersize default
\use_geometry false
\use_package amsmath 1
\use_package amssymb 1
\use_package cancel 1
\use_package esint 1
\use_package mathdots 1
\use_package mathtools 1
\use_package mhchem 1
\use_package stackrel 1
\use_package stmaryrd 1
\use_package undertilde 1
\cite_engine basic
\cite_engine_type default
\biblio_style plain
\use_bibtopic false
\use_indices false
\paperorientation portrait
\suppress_date false
\justification true
\use_refstyle 1
\use_minted 0
\index Index
\shortcut idx
\color #008000
\end_index
\secnumdepth 3
\tocdepth 3
\paragraph_separation indent
\paragraph_indentation default
\is_math_indent 0
\math_numbering_side default
\quotes_style russian
\dynamic_quotes 0
\papercolumns 1
\papersides 1
\paperpagestyle default
\tracking_changes false
\output_changes false
\html_math_output 0
\html_css_as_file 0
\html_be_strict false
\end_header

\begin_body

\begin_layout Title
Разбор упражнений и задач из 
\begin_inset Quotes rld
\end_inset

От математики к обобщённому программированию
\begin_inset Quotes rrd
\end_inset

 (А.
\begin_inset space \thinspace{}
\end_inset

Степанов, Д.
\begin_inset space \thinspace{}
\end_inset

Роуз)
\end_layout

\begin_layout Chapter
О чём эта книга
\end_layout

\begin_layout Standard
\begin_inset Note Comment
status open

\begin_layout Plain Layout
Эта глава, по сути, является введением и не содержит заданий.
\end_layout

\end_inset


\end_layout

\begin_layout Chapter
Первый алгоритм
\end_layout

\begin_layout Problem
Найти оптимальные цепочки сложения для всех 
\begin_inset Formula $n<100$
\end_inset

.
\end_layout

\begin_layout Solution
\begin_inset Note Comment
status open

\begin_layout Plain Layout
Эта задача была решена в рамках проекта Эйлер.
\end_layout

\end_inset


\end_layout

\begin_layout Chapter
Теория чисел в Древней Греции
\end_layout

\begin_layout Section
Геометрические свойства целых чисел
\end_layout

\begin_layout Standard
\begin_inset Note Note
status open

\begin_layout Plain Layout
Дать определение треугольных чисел
\end_layout

\end_inset


\end_layout

\begin_layout Standard
\begin_inset Note Note
status open

\begin_layout Plain Layout
Дать определение прямоугольных чисел
\end_layout

\end_inset


\end_layout

\begin_layout Standard
\begin_inset Note Note
status open

\begin_layout Plain Layout
Найти общую формулу для треугольных чисел через прямоугольные
\end_layout

\end_inset


\end_layout

\begin_layout Problem
Найти геометрическое доказательство следующего утверждения: если взять любое
 треугольное число, умножить его на 8 и прибавить 1, то получится квадратное
 число (эта задача взята из 
\begin_inset Quotes rld
\end_inset

Платновских вопросов
\begin_inset Quotes rrd
\end_inset

 Плутарха).
\end_layout

\begin_layout Section
Просеивание простых чисел
\end_layout

\begin_layout Definition
Пифагорейцы также заметили, что некоторые числа невозможно представить в
 виде нетривиального прямоугольника (у которого обе стороны больше 1).
 Такие числа, которые нельзя разложить в произведение меньших чисел, мы
 теперь называем 
\emph on
простыми.
\begin_inset Note Note
status open

\begin_layout Plain Layout
Здесь и в следующей теореме нужно отдельно рассмотреть единицу
\end_layout

\end_inset


\end_layout

\begin_layout Standard
\begin_inset Quotes rld
\end_inset

Числами
\begin_inset Quotes rrd
\end_inset

 древние греки называли только целые числа, других они не знали.
 
\end_layout

\begin_layout Theorem
(Евклид VII, 32).
 Любое (целое) число либо является простым, либо делится на некоторое простое
 число.
\end_layout

\begin_layout Proof
В доказательсте используется 
\begin_inset Quotes rld
\end_inset

невозможность бесконечного спуска)
\begin_inset Quotes rrd
\end_inset

.
\end_layout

\begin_layout Proof
Рассмотрим произвольное число 
\begin_inset Formula $a_{1}$
\end_inset

.
 Если оно простое, то доказательство закончено.
 Пусть теперь 
\begin_inset Formula $a_{1}$
\end_inset

 не простое, тогда оно делится на некоторое число 
\begin_inset Formula $1<a_{2}<a_{1}$
\end_inset

.
 Те же рассуждения можно применить к 
\begin_inset Formula $a_{2}$
\end_inset

 и т.д.
 Таким образом, мы получаем убывающую последовательность натуральных чисел
 
\begin_inset Formula $a_{n}$
\end_inset

 (причём 
\begin_inset Formula $a_{n}>1$
\end_inset

).
 Эта последовательность не может быть бесконечной, поэтому для некоторого
 
\begin_inset Formula $n$
\end_inset

 число 
\begin_inset Formula $a_{n}$
\end_inset

 окажется простым.
 
\end_layout

\begin_layout Proof
Таким образом 
\begin_inset Formula $a_{k}$
\end_inset

 делится на 
\begin_inset Formula $a_{k+1}$
\end_inset

 для любого 
\begin_inset Formula $k=1,\dots n-1$
\end_inset

 и 
\begin_inset Formula $a_{n}$
\end_inset

 — простое число.
 
\end_layout

\begin_layout Proof
Докажем, что если 
\begin_inset Formula $a$
\end_inset

 делится на 
\begin_inset Formula $b$
\end_inset

, а 
\begin_inset Formula $b$
\end_inset

 делится на 
\begin_inset Formula $c$
\end_inset

, то 
\begin_inset Formula $a$
\end_inset

 делится на 
\begin_inset Formula $c$
\end_inset

 (говорят, что отношение делимости является транзитивым).
 По определению, существуют целые положительные числа 
\begin_inset Formula $r$
\end_inset

 и 
\begin_inset Formula $s$
\end_inset

 большие единицы такие, что 
\begin_inset Formula $a=rb$
\end_inset

 и 
\begin_inset Formula $b=sc$
\end_inset

, но тогда 
\begin_inset Formula $a=rb=rsc=\left(rs\right)c$
\end_inset

, то есть существует такое целое положительное число 
\begin_inset Formula $t$
\end_inset

, большее единицы, такое, что 
\begin_inset Formula $a=tc$
\end_inset

 (а именно — 
\begin_inset Formula $t=rs$
\end_inset

), это означает, что 
\begin_inset Formula $a$
\end_inset

 действительно делится на 
\begin_inset Formula $c$
\end_inset

.
\end_layout

\begin_layout Proof
Таким образом, по индукции можно показать, что все 
\begin_inset Formula $a_{k}$
\end_inset

 при 
\begin_inset Formula $k=1,\dots n-1$
\end_inset

 деляться на простое число 
\begin_inset Formula $a_{n}$
\end_inset

, в частности, на это простое число делится исходное 
\begin_inset Formula $a_{1}$
\end_inset

.
\end_layout

\begin_layout Theorem
(Евклид IX, 20).
 Для любой конечной последовательности простых чисел 
\begin_inset Formula $\left\{ p_{1},\dots,p_{n}\right\} $
\end_inset

, существует простое число 
\begin_inset Formula $p$
\end_inset

, не принадлежащее этой последовательности.
\end_layout

\begin_layout Proof
Рассмотрим число 
\begin_inset Formula 
\[
q=\prod_{k=1}^{n}p_{k}+1.
\]

\end_inset


\end_layout

\begin_layout Proof
Это число не делится ни на одно из чисел 
\begin_inset Formula $p_{k}$
\end_inset

, так как для любого 
\begin_inset Formula $k$
\end_inset

 имеет место равенство 
\begin_inset Formula $q\mod p_{k}=1$
\end_inset

.
 Если 
\begin_inset Formula $q$
\end_inset

 простое число, то его можно взять за 
\begin_inset Formula $p$
\end_inset

.
 Пусть 
\begin_inset Formula $q$
\end_inset

 — не является простым, тогда оно делится на некоторое простое число, но
 как мы показали выше, это не может быть ни одно из чисел 
\begin_inset Formula $p_{k}$
\end_inset

, тогда это простое число можно взять за 
\begin_inset Formula $p$
\end_inset

.
\end_layout

\begin_layout Standard
\begin_inset Note Comment
status open

\begin_layout Plain Layout
Далее описано решето Эратосфена.
\end_layout

\end_inset


\end_layout

\begin_layout Section
Реализация и оптимизация кода
\end_layout

\begin_layout Problem
Измерьте время работы решета при разных размерах данных.
\end_layout

\begin_layout Solution
\begin_inset Note Comment
status open

\begin_layout Plain Layout
Эта задача не является математической
\end_layout

\end_inset


\end_layout

\begin_layout Problem
Пользуясь решетом, постройте график функции 
\begin_inset Quotes rld
\end_inset

количество простых чисел, меньших заданного числа 
\begin_inset Formula $n$
\end_inset


\begin_inset Quotes rrd
\end_inset

 для 
\begin_inset Formula $n<10^{7}$
\end_inset

, найдите аналитическую аппроксимацию
\end_layout

\begin_layout Solution
\begin_inset Note Comment
status open

\begin_layout Plain Layout
Эта задача не является математической
\end_layout

\end_inset


\end_layout

\begin_layout Problem
Существуют ли паландромические простые числа, большие 1000? Почему их нет
 в интервале 
\begin_inset Formula $\left[1000;2000\right]$
\end_inset

? Что произойдёт, если за основание системы счисления взять 16? А если произволь
ное число 
\begin_inset Formula $n$
\end_inset

?
\end_layout

\begin_layout Solution
Рассмотрим палиндромическое число из интервала 
\begin_inset Formula $\left[1000;2000\right]$
\end_inset

.
 Оно имеет в десятичной записи вид 
\begin_inset Formula $1aa1$
\end_inset

, где 
\begin_inset Formula $a$
\end_inset

 — некоторая цифра.
 Это число выражается как 
\begin_inset Formula $1000+100a+10a+1=1001+110a$
\end_inset

.
 Это число делится на 
\begin_inset Formula $11$
\end_inset

, действительно, 
\begin_inset Formula $1001=11\cdot91$
\end_inset

, а 
\begin_inset Formula $110a=11\cdot10a$
\end_inset

.
 Таким образом, любое палиндромическое число из интервала 
\begin_inset Formula $\left[1000;2000\right]$
\end_inset

 делится на 
\begin_inset Formula $11$
\end_inset

.
\end_layout

\begin_layout Solution
\begin_inset Note Note
status open

\begin_layout Plain Layout
Ответить на остальные вопросы
\end_layout

\end_inset


\end_layout

\begin_layout Section
Совершенные числа
\end_layout

\begin_layout Standard
Собственным делителем числа 
\begin_inset Formula $n$
\end_inset

 называется любой его делитель, отличный от него самого.
\end_layout

\begin_layout Standard
Совершенное число — число, равное сумме своих сосбвтенных делителей.
\end_layout

\begin_layout Standard
Древним грекам было известно четыре совершенных числа: 
\begin_inset Formula $6$
\end_inset

, 
\begin_inset Formula $28$
\end_inset

, 
\begin_inset Formula $496$
\end_inset

, 
\begin_inset Formula $8128$
\end_inset

.
\end_layout

\begin_layout Standard
Можно обнаружить следующую закономерность: 
\begin_inset Formula 
\begin{multline*}
6=2\cdot3=2^{1}\cdot\left(2^{2}-1\right)\\
28=4\cdot7=2^{2}\cdot\left(2^{3}-1\right)\\
120=8\cdot15=2^{3}\cdot\left(2^{4}-1\right)\\
496=16\cdot31=2^{4}\cdot\left(2^{5}-1\right)\\
2016=32\cdot63=2^{5}\cdot\left(2^{6}-1\right)\\
8128=64\cdot127=2^{6}\cdot\left(2^{7}-1\right)
\end{multline*}

\end_inset


\end_layout

\begin_layout Standard
В этой последовательности число является совершенным, если второй сомножитель
 явлется простым.
\end_layout

\begin_layout Theorem
Если 
\begin_inset Formula $\sum_{k=0}^{n}2^{k}$
\end_inset

 — простое число, то 
\begin_inset Formula $2^{n}\sum_{k=0}^{n}2^{k}$
\end_inset

 — совершенное число.
\end_layout

\begin_layout Standard
Для доказательства этой теоремы рассмотрим серию задач.
\end_layout

\begin_layout Standard
\begin_inset Note Note
status open

\begin_layout Plain Layout
Доказать, что 
\begin_inset Formula $\sum_{k=0}^{n}2^{k}=2^{n+1}-1$
\end_inset

.
 Это равенство следует из 
\begin_inset Formula $a^{n}-b^{n}=\left(a-b\right)\left(\sum_{k=0}^{n-1}a^{k}b^{n-k}\right)$
\end_inset


\end_layout

\end_inset


\end_layout

\begin_layout Standard
С учётом этого, теорему можно переформулировать следующим образом: 
\emph on
Если 
\begin_inset Formula $2^{n}-1$
\end_inset

 — простое число, то 
\begin_inset Formula $2^{n-1}\left(2^{n}-1\right)$
\end_inset

 — совершенное число.
\end_layout

\begin_layout Problem
Если 
\begin_inset Formula $2^{n}-1$
\end_inset

 простое число, то 
\begin_inset Formula $n$
\end_inset

 — простое число.
\end_layout

\begin_layout Solution*
Докажем контр-оппозицию этого утверждения, то есть, из того, что 
\begin_inset Formula $n$
\end_inset

 — не простое число, выведем, что 
\begin_inset Formula $2^{n}-1$
\end_inset

 — также не простое число.
 
\end_layout

\begin_layout Solution*
Пусть 
\begin_inset Formula $n$
\end_inset

 — не является простым, то есть может быть представлено в виде 
\begin_inset Formula $n=ab$
\end_inset

, где 
\begin_inset Formula $1<a<n$
\end_inset

 и 
\begin_inset Formula $1<b<n$
\end_inset

, тогда 
\begin_inset Formula 
\[
2^{n}-1=2^{ab}-1=\left(2^{a}\right)^{b}-1^{b}=\left(2^{a}-1\right)\sum_{k=0}^{b-1}2^{ak}.
\]

\end_inset

 Так как 
\begin_inset Formula $a>1$
\end_inset

, то 
\begin_inset Formula $2^{a}-1>1$
\end_inset

, то есть у 
\begin_inset Formula $2^{n}-1$
\end_inset

 есть делители, отличные от 
\begin_inset Formula $1$
\end_inset

 и 
\begin_inset Formula $2^{n}-1$
\end_inset

.
 Утверждение доказано, а вместе с ним и исходное утверждение задачи.
\end_layout

\begin_layout Standard
Обозначим сумму делителей числа 
\begin_inset Formula $n$
\end_inset

 как 
\begin_inset Formula $\sigma\left(n\right)$
\end_inset

.
\end_layout

\begin_layout Standard
Пусть 
\begin_inset Formula $n=p_{1}$
\end_inset

 — простое число.
 Тогда делителями 
\begin_inset Formula $n$
\end_inset

 являются числа 
\begin_inset Formula $1$
\end_inset

 и 
\begin_inset Formula $p_{1}=n$
\end_inset

.
 Тогда 
\begin_inset Formula $\sigma\left(n\right)=1+p_{1}$
\end_inset

.
\end_layout

\begin_layout Standard
Пусть теперь 
\begin_inset Formula $n=p_{1}^{a_{1}}$
\end_inset

, где 
\begin_inset Formula $p_{1}$
\end_inset

 — простое число и 
\begin_inset Formula $a_{1}$
\end_inset

 — целое положительное число.
 Тогда делителями 
\begin_inset Formula $n$
\end_inset

 являются 
\begin_inset Formula $p_{1}^{k}$
\end_inset

 при 
\begin_inset Formula $k=0,1,\dots a_{1}$
\end_inset

 и 
\begin_inset Formula 
\[
\sigma\left(n\right)=\sum_{k=0}^{a_{1}}p_{1}^{k},
\]

\end_inset

 тогда, по формуле суммы геометрической прогрессии: 
\begin_inset Formula 
\[
\sigma\left(n\right)=\frac{p_{1}^{a_{1}+1}-1}{p_{1}-1}.
\]

\end_inset


\end_layout

\begin_layout Standard
Для нахождения формулы в общем случае, рассмотрим сначала одно свойство
 функции 
\begin_inset Formula $\sigma$
\end_inset

.
\end_layout

\begin_layout Problem
Докажите, что если 
\begin_inset Formula $n$
\end_inset

 и 
\begin_inset Formula $m$
\end_inset

 — взаимно простые числа (то есть не имеющие общих делителей, кроме 
\begin_inset Formula $1$
\end_inset

), то 
\begin_inset Formula 
\[
\sigma\left(mn\right)=\sigma\left(m\right)\sigma\left(n\right).
\]

\end_inset

 (говорят, что 
\begin_inset Formula $\sigma$
\end_inset

 — мультипликативная функция).
\end_layout

\begin_layout Solution
Пусть делители 
\begin_inset Formula $m$
\end_inset

 — это числа 
\begin_inset Formula $d_{0}=1,d_{1},\dots,d_{r},d_{r+1}=m$
\end_inset

, а делители 
\begin_inset Formula $n$
\end_inset

 — это 
\begin_inset Formula $g_{0}=1,g_{1},\dots,g_{s},g_{s+1}=n$
\end_inset

.
 Тогда можно написать 
\begin_inset Formula 
\[
\sigma\left(m\right)=\sum_{i=1}^{r+1}d_{i},
\]

\end_inset


\begin_inset Formula 
\[
\sigma\left(n\right)=\sum_{j=1}^{s+1}g_{j}.
\]

\end_inset


\end_layout

\begin_layout Solution
Так как у 
\begin_inset Formula $n$
\end_inset

 и 
\begin_inset Formula $m$
\end_inset

 нет общих делителей, то делители 
\begin_inset Formula $mn$
\end_inset

 имеют вид 
\begin_inset Note Note
status open

\begin_layout Plain Layout
возможно, это нужно доказать подробнее
\end_layout

\end_inset


\begin_inset Formula 
\[
d_{i}g_{j},
\]

\end_inset

 где 
\begin_inset Formula $0\le i\le r+1$
\end_inset

 и 
\begin_inset Formula $0\le j\le s+1$
\end_inset

, тогда 
\begin_inset Formula 
\[
\sigma\left(nm\right)=\sum_{i=0}^{r+1}\sum_{j=0}^{s+1}d_{i}g_{j}.
\]

\end_inset

 Так как 
\begin_inset Formula $d_{i}$
\end_inset

 не зависит от индекса 
\begin_inset Formula $j$
\end_inset

, то его можно вынести из под внутренней суммы: 
\begin_inset Formula 
\[
\sigma\left(nm\right)=\sum_{i=0}^{r+1}d_{i}\sum_{j=0}^{s+1}g_{j}=\sum_{i=0}^{r+1}d_{i}\sigma\left(n\right)=\sigma\left(n\right)\sum_{i=0}^{r+1}d_{i}=\sigma\left(n\right)\sigma\left(m\right),
\]

\end_inset

 что и требовалось.
\end_layout

\begin_layout Standard
Пусть теперь 
\begin_inset Formula $n$
\end_inset

 — произвольное натуральное число, большее 
\begin_inset Formula $1$
\end_inset

, тогда, по основной теореме арифметики 
\begin_inset Note Note
status open

\begin_layout Plain Layout
Написать про неё и сослаться
\end_layout

\end_inset

, его можно представить в виде 
\begin_inset Formula 
\[
n=\prod_{i=1}^{r}p_{i}^{a_{i}},
\]

\end_inset

где 
\begin_inset Formula $p_{i}$
\end_inset

 — простые числа, 
\begin_inset Formula $a_{i}$
\end_inset

 — положительные целые числа.
 По доказанному выше, 
\begin_inset Formula 
\[
\sigma\left(n\right)=\prod_{i=1}^{r}\sigma\left(p_{i}^{a_{i}}\right)=\prod_{i=1}^{r}\frac{p_{i}^{a_{i}+1}-1}{p_{i}-1}.
\]

\end_inset


\end_layout

\begin_layout Standard
Наконец, рассмотрим сумму собственных делителей числа 
\begin_inset Formula $n$
\end_inset

 (аликвотная сумма): 
\begin_inset Formula 
\[
\alpha\left(n\right)=\sigma\left(n\right)-n.
\]

\end_inset


\end_layout

\begin_layout Standard
Для доказательства теоремы нужно доказать, что когда 
\begin_inset Formula $\left(2^{n}-1\right)$
\end_inset

 — простое число, то 
\begin_inset Formula $\alpha\left(2^{n-1}\left(2^{n}-1\right)\right)=2^{n-1}\left(2^{n}-1\right)$
\end_inset

.
 Действительно, пусть 
\begin_inset Formula $2^{n}-1$
\end_inset

 — простое число, тогда 
\begin_inset Formula $2^{n-1}<2^{n}-1$
\end_inset

 (при 
\begin_inset Formula $n>1)$
\end_inset

 и 
\begin_inset Formula $2^{n-1}$
\end_inset

 и 
\begin_inset Formula $2^{n}-1$
\end_inset

 взаимно просты.
 Поэтому 
\begin_inset Formula 
\begin{multline*}
\sigma\left(2^{n-1}\left(2^{n}-1\right)\right)=\sigma\left(2^{n-1}\right)\sigma\left(2^{n}-1\right)=\\
=\frac{2^{n}-1}{2-1}\cdot\left(2^{n}-1+1\right)=\left(2^{n}-1\right)\cdot2^{n},
\end{multline*}

\end_inset

тогда 
\begin_inset Formula 
\[
\alpha\left(2^{n-1}\left(2^{n}-1\right)\right)=2^{n}\left(2^{n}-1\right)-2^{n-1}\left(2^{n}-1\right)=2^{n-1}\left(2^{n}-1\right),
\]

\end_inset

 то есть 
\begin_inset Formula $2^{n-1}\left(2^{n}-1\right)$
\end_inset

 действительно является совершенным числом.
\end_layout

\begin_layout Standard
Теорема Евклида утверждает, что если число имеет определённый вди, то оно
 совершенное.
 Возникает интересный вопрос: верно ли обратное, то есть правда ли, что
 если число совершенное, то оно имеет вид 
\begin_inset Formula $2^{n-1}\left(2^{n}-1\right)$
\end_inset

? В XVIII веке Эйлер доказал, что всякое чётное совершенное число действительно
 имеет такой вид.
 Но он не смог доказать более общий результат — что 
\emph on
любое 
\emph default
совершенное число имеет такой вид.
 Эта проблема и по сей день остаётся нерешённой, мы не знаем, существуют
 ли нечётные совершенные числа.
\end_layout

\begin_layout Problem
Докажите, что любое чётное совершенное число является треугольным.
\end_layout

\begin_layout Solution
Треугольные числа имеют вид 
\begin_inset Formula 
\[
\frac{m\left(m-1\right)}{2}.
\]

\end_inset

Пусть 
\begin_inset Formula $a$
\end_inset

 — чётное соврешенное число.
 Тогда, по доказанному Эйлером
\begin_inset Note Note
status open

\begin_layout Plain Layout
Может быть это надо доказать тоже?
\end_layout

\end_inset

, 
\begin_inset Formula $a=2^{n-1}\left(2^{n}-1\right)$
\end_inset

 и 
\begin_inset Formula 
\[
a=\frac{2^{n}\left(2^{n}-1\right)}{2},
\]

\end_inset

таким образом, если положить 
\begin_inset Formula $m=2^{n}$
\end_inset

, то мы увидим, что 
\begin_inset Formula $a$
\end_inset

 действительно является треугольным числом.
\end_layout

\begin_layout Problem
Докажите, что сумма числе, обратных делителям соверешнного числа, равна
 
\begin_inset Formula $2$
\end_inset

.
 Например: 
\begin_inset Formula 
\[
1+\frac{1}{2}+\frac{1}{3}+\frac{1}{6}=2.
\]

\end_inset


\end_layout

\begin_layout Solution
Рассмотрим произвольное совершенное число 
\begin_inset Formula $n$
\end_inset

, пусть его делители есть 
\begin_inset Formula $d_{0}=1,d_{1},\dots,d_{r},d_{r+1}=n$
\end_inset

, тогда, поскольку 
\begin_inset Formula $n$
\end_inset

 — совершенное число, то
\begin_inset Formula 
\[
\sigma\left(n\right)=\sum_{i=0}^{r+1}d_{i}=2n,
\]

\end_inset

 разделим это равенство на 
\begin_inset Formula $n$
\end_inset

, получим 
\begin_inset Formula 
\[
\sum_{i=0}^{r+1}\frac{d_{i}}{n}=2,
\]

\end_inset

 но если 
\begin_inset Formula $d_{i}$
\end_inset

 является делителем 
\begin_inset Formula $n$
\end_inset

, то 
\begin_inset Formula 
\[
\frac{n}{d_{i}}=d_{j_{i}},
\]

\end_inset

где 
\begin_inset Formula $d_{j_{i}}$
\end_inset

 — некоторый другой делитель числа 
\begin_inset Formula $n$
\end_inset

, причём при разных 
\begin_inset Formula $d_{i}$
\end_inset

 будем получать разные 
\begin_inset Formula $d_{j_{i}}$
\end_inset

, то есть 
\begin_inset Formula $d_{j_{0}},\dots d_{j_{r+1}}$
\end_inset

 является перестановкой чисел 
\begin_inset Formula $d_{0},\dots d_{r+1}$
\end_inset

.
 Таким образом, 
\begin_inset Formula 
\[
\sum_{i=0}^{r+1}\frac{d_{i}}{n}=\sum_{i=0}^{r+1}\frac{1}{d_{j_{i}}}=\sum_{i=1}^{r+1}\frac{1}{d_{i}}=2,
\]

\end_inset

 что требовалось.
 
\end_layout

\begin_layout Section
Пифагорейская программа
\end_layout

\begin_layout Standard
\begin_inset Note Note
status open

\begin_layout Plain Layout
Этот раздел не содержит упражнений и теорем
\end_layout

\end_inset


\end_layout

\begin_layout Section
Фатальный изъян в программе
\end_layout

\begin_layout Standard
Греческие математики обнаружили, что принцип 
\emph on
полного упорядочения 
\emph default
— тот факт, что любое множество натуарльных чисел имеет наименьший элемент,
 — можно положить в основу эффективной техники доказательства.
 Чтобы доказать, что нечто не существует, нужно доказать, что если бы оно
 существовало, то существовало бы и нечто меньшее.
\end_layout

\begin_layout Standard
Пользуясь этой логикой, пифагорейцы обнаружили доказательство, которое подрывало
 всю их программу (Мы не знаем, сам ли Пифагор совершил это открытие или
 кто-то из его ранних учеников).
\end_layout

\begin_layout Theorem
Не существует отрезка, который мог бы служить мерой для стороны квадрата
 и его диагонали.
\end_layout

\begin_layout Standard
\begin_inset Note Note
status open

\begin_layout Plain Layout
Это геометрическая задача, нужно придумать, как упростить создание чертежей,
 поэтому пока пропустим доказательство этой теоремы
\end_layout

\end_inset


\end_layout

\begin_layout Standard
Иными словами, отношение диагонали квадрата к его стороне невозможно выразить
 рациональным числом (отношением двух целых чисел).
 Сегодня мы сказали бы, что пифагорейцы открыли иррациональные числа, а
 точнее доказали, что число 
\begin_inset Formula $\sqrt{2}$
\end_inset

 иррационально.
\end_layout

\begin_layout Standard
Открытие иррациональных чисел стало глубочайшим потрясением.
 Оно подрывало всю программу пифагорейцев и означало, что числа не могут
 быть положены в основу геометрии.
 Поэтому пифагорейцы сделали то же самое, что и многие организации, сталкивающие
ся с плохими известиями: все засекретили.
 Легенда гласит, что когда из членов ордена рассказал кому-то это историю,
 боги покарали его, потопив корабль, на котором оп плыл со всеми, кто был
 на борту.
\end_layout

\begin_layout Standard
В конечном итоге последователи пифагорейцы придумали другую стратегию.
 Если невозможно построить математику на основе чисел, то следует положить
 в её основу геометрию.
 К этой идее восходят построения помощью циркуля и линейки, которые до сих
 пор используют в школе при изучении геометрии, числа в них не используются
 и не требуются.
\end_layout

\begin_layout Standard
Позже математики нашли другие, теоретико числовые доказательства иррациональност
и 
\begin_inset Formula $\sqrt{2}$
\end_inset

.
 Одно из них включено в виде предложения 11 в некоторые издания книги X
 
\begin_inset Quotes rld
\end_inset

Начал
\begin_inset Quotes rrd
\end_inset

 Евклида.
 И хотя это доказательство было найдено ещё до Евклида, в 
\begin_inset Quotes rld
\end_inset

Начало
\begin_inset Quotes rrd
\end_inset

 оно было добавлено спустя некоторое время после выхода первого издания.
 Как бы то ни было, это доказательство важно.
\end_layout

\begin_layout Theorem
Число 
\begin_inset Formula $\sqrt{2}$
\end_inset

 иррационально.
\end_layout

\begin_layout Proof
Доказательство проведём от противного.
 Пусть 
\begin_inset Formula $\sqrt{2}$
\end_inset

 — есть рациональное число, тогда существуют такие положительные целые числа
 
\begin_inset Formula $m$
\end_inset

 и 
\begin_inset Formula $n$
\end_inset

, что 
\begin_inset Formula 
\[
\frac{m}{n}=\sqrt{2},
\]

\end_inset

 без ограничения общности можно считать, что эти числа взаимно просты (в
 противном случае, мы могли бы сократить на общий множитель).
 Возведём это равенство в квадрат: 
\begin_inset Formula 
\[
\frac{m^{2}}{n^{2}}=2
\]

\end_inset

или 
\begin_inset Formula 
\[
m^{2}=2n^{2}.
\]

\end_inset

 Из этого равенства следует, что 
\begin_inset Formula $m$
\end_inset

 — чётное число, то есть 
\begin_inset Formula $m=2m_{1}$
\end_inset

, где 
\begin_inset Formula $m_{1}<m$
\end_inset

, поэтому 
\begin_inset Formula 
\[
2n^{2}=\left(2m_{1}\right)^{2}=4m_{1}^{2}
\]

\end_inset

или 
\begin_inset Formula 
\[
n^{2}=2m_{1}^{2},
\]

\end_inset

то есть 
\begin_inset Formula $n$
\end_inset

 также является чётным числом.
 Таким образом, оба числа 
\begin_inset Formula $m$
\end_inset

 и 
\begin_inset Formula $n$
\end_inset

 являются чётными, но это противоречит предположению о том, что у них нет
 общих множителей.
 Таким образом, 
\begin_inset Formula $\sqrt{2}$
\end_inset

 — иррациональное число.
\end_layout

\begin_layout Proof
\begin_inset Note Note
status open

\begin_layout Plain Layout
Возможно, нужно отдельно доказать, что чётность числа сохраняется при возведении
 его в квадрат
\end_layout

\end_inset

 
\end_layout

\begin_layout Chapter
Алгоритм Евклида
\end_layout

\begin_layout Section
Афины и Александрия
\end_layout

\begin_layout Standard
\begin_inset Note Comment
status open

\begin_layout Plain Layout
Чисто исторический раздел
\end_layout

\end_inset


\end_layout

\begin_layout Section
Алгоритм Евклида нахождения общей меры
\end_layout

\begin_layout Standard
\begin_inset Note Note
status open

\begin_layout Plain Layout
Проработать этот раздел
\end_layout

\end_inset


\end_layout

\begin_layout Problem
Функция gcm0 неэффективна, когда один отрезок намного длиннее другого.
 Предложите более эффективную реализацию.
 Помните, что запрещено использовать операции, которые нельзя выполнить
 с помощью циркуля и линейки.
\end_layout

\begin_layout Solution
\begin_inset Note Note
status open

\begin_layout Plain Layout
Программная задача.
 Написать решение
\end_layout

\end_inset


\end_layout

\begin_layout Problem
Докажите, что если некоторые отрезок измеряет два других отрезка, то он
 измеряет и их наибольшую общую меру.
\end_layout

\begin_layout Solution
\begin_inset Note Note
status open

\begin_layout Plain Layout
Написать решение
\end_layout

\end_inset


\end_layout

\begin_layout Section
Тысяча лет без математики
\end_layout

\begin_layout Standard
\begin_inset Note Comment
status open

\begin_layout Plain Layout
Чисто исторический раздел
\end_layout

\end_inset


\end_layout

\begin_layout Section
Странная история нуля
\end_layout

\begin_layout Problem
Докажите, что 
\begin_inset Formula $\sqrt[3]{16}+\sqrt[3]{54}=\sqrt[3]{250}.$
\end_inset


\end_layout

\begin_layout Solution
Заметим, что 
\begin_inset Formula $16=2^{4}$
\end_inset

 и 
\begin_inset Formula $54=2\cdot3^{3}$
\end_inset

.
 Возведём левую часть рассматриваемого равенства в куб, по формуле куба
 суммы: 
\begin_inset Formula 
\begin{multline*}
\left(\sqrt[3]{16}+\sqrt[3]{54}\right)^{3}=\\
=\left(\sqrt[3]{16}\right)^{3}+3\left(\sqrt[3]{16}\right)^{2}\sqrt[3]{54}+3\sqrt[3]{16}\left(\sqrt[3]{54}\right)^{2}+\left(\sqrt[3]{54}\right)^{3}=\\
=16+3\sqrt[3]{16^{2}\cdot54}+3\sqrt[3]{16\cdot54^{2}}+54=\\
=16+3\sqrt[3]{\left(2^{4}\right)^{2}\cdot2\cdot3^{3}}+3\sqrt[3]{2\cdot2^{3}\cdot2^{2}\cdot3^{6}}+54=\\
=16+3\sqrt[3]{2^{9}\cdot3^{3}}+3\sqrt[3]{2^{6}3^{6}}+54=\\
=16+3\cdot2^{3}\cdot3+3\cdot2^{2}\cdot3^{2}+54=\\
=16+72+108+54=250.
\end{multline*}

\end_inset


\end_layout

\begin_layout Solution
Так как 
\begin_inset Formula $\left(\sqrt[3]{16}+\sqrt[3]{54}\right)^{3}=250$
\end_inset

, то 
\begin_inset Formula $\sqrt[3]{16}+\sqrt[3]{54}=\sqrt[3]{250}$
\end_inset

.
 Что и требовалось.
 
\end_layout

\begin_layout Solution
\begin_inset Note Note
status open

\begin_layout Plain Layout
Здесь можно было бы ещё доказать, что у вещественного числа может быть только
 один вещественный корень
\end_layout

\end_inset


\end_layout

\begin_layout Problem
Докажите следующее утверждение из 
\begin_inset Quotes rld
\end_inset

Книги квадратов
\begin_inset Quotes rrd
\end_inset

: для любого нечётного квадратного числа 
\begin_inset Formula $x$
\end_inset

 найдётся чётное квадратное число 
\begin_inset Formula $y$
\end_inset

, такое, что 
\begin_inset Formula $x+y$
\end_inset

 — квадратное число.
\end_layout

\begin_layout Solution
Рассмотрим произвольное нечётное квадратное число 
\begin_inset Formula $y$
\end_inset

.
 Так как квадрат чётного числа – это чётное число, а квадрат нечётного числа
 — нечётное число
\begin_inset Note Note
status open

\begin_layout Plain Layout
Доказать?
\end_layout

\end_inset

, то 
\begin_inset Formula $y$
\end_inset

 имеет вид 
\begin_inset Formula $y=\left(2k+1\right)^{2}$
\end_inset

, где 
\begin_inset Formula $k$
\end_inset

 — произвольное натуральное число (в том числе — ноль).
 Любое нечётное число можно представить как разность квадратов двух соседних
 натуральных чисел: 
\begin_inset Formula 
\[
\left(k+1\right)^{2}-k^{2}=k^{2}+2k+1-k^{2}=2k+1,
\]

\end_inset

 то есть 
\begin_inset Formula 
\[
y=\left(\left(k+1\right)^{2}-k^{2}\right)^{2}=\left(k+1\right)^{4}-2\left(k+1\right)^{2}k^{2}+k^{4}.
\]

\end_inset

Положим теперь 
\begin_inset Formula $x=4\left(k+1\right)^{2}k^{2}=\left(2\left(k+1\right)k\right)^{2}$
\end_inset

.
 Очевидно, что это число является квадратом, притом целым.
 Тогда получим 
\begin_inset Formula 
\[
x+y=\left(k+1\right)^{4}+2\left(k+1\right)^{2}k^{2}+k^{4}=\left(\left(k+1\right)^{2}+k^{2}\right)^{2},
\]

\end_inset

 то есть 
\begin_inset Formula $x+y$
\end_inset

 также будет квадратом.
\end_layout

\begin_layout Problem
Докажите следующее утверждение из 
\begin_inset Quotes rld
\end_inset

Книги квадратов
\begin_inset Quotes rrd
\end_inset

: если 
\begin_inset Formula $x$
\end_inset

 и 
\begin_inset Formula $y$
\end_inset

 — суммы двух квадратов, то таким же будет и их произведение 
\begin_inset Formula $xy$
\end_inset

 (это важный результат, на который опирался ферма).
\end_layout

\begin_layout Solution
По условию 
\begin_inset Formula $x=m^{2}+n^{2}$
\end_inset

 и 
\begin_inset Formula $y=s^{2}+t^{2}$
\end_inset

, где 
\begin_inset Formula $m$
\end_inset

, 
\begin_inset Formula $n$
\end_inset

, 
\begin_inset Formula $s$
\end_inset

 и 
\begin_inset Formula $t$
\end_inset

 — целые числа.
 Тогда 
\begin_inset Formula 
\[
xy=\left(m^{2}+n^{2}\right)\left(s^{2}+t^{2}\right)=m^{2}s^{2}+m^{2}t^{2}+n^{2}s^{2}+n^{2}t^{2}.
\]

\end_inset

 Добавим и вычтем из этого выражения 
\begin_inset Formula $2mnst$
\end_inset

, а затем перегруппируем слагаемые: 
\begin_inset Formula 
\begin{multline*}
xy=m^{2}s^{2}+m^{2}t^{2}+n^{2}s^{2}+n^{2}t^{2}+2mnst-2mnst=\\
=m^{2}s^{2}+2mnst+n^{2}t^{2}+m^{2}t^{2}-2mtns+n^{2}s^{2}=\\
=\left(ms+nt\right)^{2}+\left(mt-ns\right)^{2},
\end{multline*}

\end_inset

 то есть 
\begin_inset Formula $xy$
\end_inset

 действительно является суммой двух квадратов.
\end_layout

\begin_layout Standard
\begin_inset Note Note
status open

\begin_layout Plain Layout
Закончить эту главу
\end_layout

\end_inset


\end_layout

\begin_layout Chapter
Зарождение современной теории чисел
\end_layout

\begin_layout Section
Простые числа Мерсенна и Ферма
\end_layout

\begin_layout Standard
\begin_inset Note Note
status open

\begin_layout Plain Layout
Пропущена вводная часть
\end_layout

\end_inset


\end_layout

\begin_layout Theorem
Если 
\begin_inset Formula $2^{n}-1$
\end_inset

 — простое число, то 
\begin_inset Formula $n$
\end_inset

 — простое.
\end_layout

\begin_layout Proof
\begin_inset Note Note
status open

\begin_layout Plain Layout
Доказательство было выше, в упражнении 3.5
\end_layout

\end_inset


\end_layout

\begin_layout Theorem
Если 
\begin_inset Formula $2^{n}+1$
\end_inset

 — простое число, то 
\begin_inset Formula $n=2^{k}$
\end_inset

.
\end_layout

\begin_layout Proof
Предположим, что 
\begin_inset Formula $n\neq2^{k}$
\end_inset

, тогда у 
\begin_inset Formula $n$
\end_inset

 должен быть нечётный сомножитель, запишем его как 
\begin_inset Formula $2q+1$
\end_inset

, то есть 
\begin_inset Formula $n=m\left(2q+1\right)$
\end_inset

, причём 
\begin_inset Formula $2q+1>1$
\end_inset

.
 По формуле суммы нечётных степеней 
\begin_inset Note Note
status open

\begin_layout Plain Layout
Нужно вывести формулу для суммы нечётных степеней и сослаться на неё
\end_layout

\end_inset

:
\begin_inset Formula 
\begin{multline*}
2^{n}+1=2^{m\left(2q+1\right)}+1=\\
=\left(2^{m}\right)^{\left(2q+1\right)}+1^{\left(2q+1\right)}=\\
=\left(2^{m}+1\right)\left(\sum_{i=0}^{2q}\left(2^{m}\right)^{i}\left(-1\right)^{i}\right).
\end{multline*}

\end_inset

 Но если любая из скобок отлична от единицы, то у 
\begin_inset Formula $2^{n}+1$
\end_inset

 есть нетривиальные делители, то есть оно не будет простым.
 Таким образом, наше предположение ложно и 
\begin_inset Formula $n=2^{i}$
\end_inset

.
\end_layout

\begin_layout Proof
Что можно сказать о других простых числа вида 
\begin_inset Formula $2^{2^{i}}+1$
\end_inset

? Ферма утверждал, что числа 3, 5, 17, 257, 65537, 4294967297 и 1844674407370955
1617 простые, а, значит, простыми являются и все остальные числа такого
 вида.
 К сожалению, он был не прав как в части двух примеров (простыми являются
 только первые пять из названных им чисел), так и в части утверждения в
 целом.
 В 1732 году Эйлер показала, что 
\begin_inset Formula 
\[
2^{32}+1=4294967297=641\times6700417.
\]

\end_inset


\end_layout

\begin_layout Proof
На самом деле мы знаем, что для всех 
\begin_inset Formula $5\le i\le32$
\end_inset

 числа Ферма составные.
 Существуют ли ещё какие-нибудь числа Ферма, кроме первых пяти? Пока никто
 не знает.
\end_layout

\begin_layout Section
Малая теорема Ферма
\end_layout

\begin_layout Theorem
(малая теорема Ферма).
 Если 
\begin_inset Formula $p$
\end_inset

 — простое, то 
\begin_inset Formula $a^{p-1}-1$
\end_inset

 делится на 
\begin_inset Formula $p$
\end_inset

 для любого 
\begin_inset Formula $0<a<p$
\end_inset

.
\end_layout

\begin_layout Standard
Для доказательства этой теоремы нужно рассмотреть несколько промежуточных
 результатов.
\end_layout

\begin_layout Theorem
(Евклид VII, 30).
 Произведение двух целых чисел, меньших простого числа 
\begin_inset Formula $p$
\end_inset

, не делится на 
\begin_inset Formula $p$
\end_inset

.
\end_layout

\begin_layout Proof
Пусть 
\begin_inset Formula $a$
\end_inset

 и 
\begin_inset Formula $b$
\end_inset

 — целые числа и 
\begin_inset Formula $0<a,b<p$
\end_inset

.
 Нужно доказать, что 
\begin_inset Formula $ab$
\end_inset

 не делится на 
\begin_inset Formula $p$
\end_inset

.
 
\end_layout

\begin_layout Proof
Так как 
\begin_inset Formula $a$
\end_inset

 и 
\begin_inset Formula $p$
\end_inset

 — взаимно простые, то существуют такие целые числа 
\begin_inset Formula $m$
\end_inset

 и 
\begin_inset Formula $n$
\end_inset

, что 
\begin_inset Formula $ma+np=1$
\end_inset

.
 
\begin_inset Note Note
status open

\begin_layout Plain Layout
Здесь нужно сослаться на 
\begin_inset Quotes rld
\end_inset

лемму о кузнечике
\begin_inset Quotes rrd
\end_inset


\end_layout

\end_inset

 Умножим это равенство на 
\begin_inset Formula $b$
\end_inset

: 
\begin_inset Formula 
\[
mab+nbp=b.
\]

\end_inset

 Если 
\begin_inset Formula $ab$
\end_inset

 делится на 
\begin_inset Formula $p$
\end_inset

, то есть 
\begin_inset Formula $ab=kp$
\end_inset

, то 
\begin_inset Formula $b=\left(mk+nb\right)p$
\end_inset

, то есть 
\begin_inset Formula $b$
\end_inset

 делится на 
\begin_inset Formula $p$
\end_inset

, но это невозможно, так как 
\begin_inset Formula $b<p$
\end_inset

 по условию задачи.
\end_layout

\begin_layout Proof
Рассмотрим ещё одно доказательство, не опирающееся на другие предположения.
 Пойдём от противного: предположим, что существует такие 
\begin_inset Formula $a$
\end_inset

 и 
\begin_inset Formula $b$
\end_inset

, что 
\begin_inset Formula $ab$
\end_inset

 делится на 
\begin_inset Formula $p$
\end_inset

.
 Пусть для данного 
\begin_inset Formula $a$
\end_inset

 число 
\begin_inset Formula $b$
\end_inset

 — это наименьшее целое число такое, что 
\begin_inset Formula $ab=mp$
\end_inset

.
 Так как 
\begin_inset Formula $p$
\end_inset

 — простое, то оно не делится на 
\begin_inset Formula $b$
\end_inset

 без остатка, поэтому
\begin_inset Formula 
\[
p=kb+r,0<r<b.
\]

\end_inset


\end_layout

\begin_layout Proof
Тогда 
\begin_inset Formula $r=p-kb$
\end_inset

 и 
\begin_inset Formula 
\[
ar=pa-kab=pa-kmp=\left(a-km\right)p,
\]

\end_inset

 то есть 
\begin_inset Formula $ar$
\end_inset

 делится на 
\begin_inset Formula $p$
\end_inset

, но 
\begin_inset Formula $r>b$
\end_inset

, но это противоречит тому, что 
\begin_inset Formula $b$
\end_inset

 наименьшее из таких чисел.
 Таким образом, предположение не верно и 
\begin_inset Formula $ab$
\end_inset

 не делится на 
\begin_inset Formula $p$
\end_inset

.
\end_layout

\begin_layout Proof
Такой метод доказательства типичен для древнегреческой математики.
 Он основан на невозможности существования бесконечной убывающей последовательно
сти натуральных чисел.
\end_layout

\begin_layout Lemma
(Лемма о перестановке остатков).
 Если 
\begin_inset Formula $p$
\end_inset

 — простое, то для любого 
\begin_inset Formula $0<a<p$
\end_inset

 
\begin_inset Formula 
\[
a\cdot\left\{ 1,\dots,p-1\right\} =\left\{ q_{1}p+r_{1},\dots,q_{p-1}p+r_{p-1}\right\} ,
\]

\end_inset

где 
\begin_inset Formula $0<r_{j}<p_{j}$
\end_inset

 при 
\begin_inset Formula $0<j<p$
\end_inset

.
 Тогда из 
\begin_inset Formula $i\neq j$
\end_inset

 следует 
\begin_inset Formula $r_{i}\neq r_{j}$
\end_inset

.
 
\end_layout

\begin_layout Lemma
Иными словами, если взять все кратные 
\begin_inset Formula $a$
\end_inset

 от 
\begin_inset Formula $1\cdot a$
\end_inset

 до 
\begin_inset Formula $\left(p-1\right)a$
\end_inset

 и поделить каждое из них с остатком на 
\begin_inset Formula $p$
\end_inset

, то все остатки будут различны, причём множество остатков является перестановко
й множества 
\begin_inset Formula $\left\{ 1,\dots,p-1\right\} $
\end_inset

 (каждый остаток меньше 
\begin_inset Formula $p$
\end_inset

, но больше нуля, все они разные).
\end_layout

\begin_layout Proof
Пусть 
\begin_inset Formula $i\neq j$
\end_inset

, но 
\begin_inset Formula $r_{i}=r_{j}$
\end_inset

, без ограничения общности можно считать, что 
\begin_inset Formula $i<j$
\end_inset

, поэтому 
\begin_inset Formula 
\[
aj-ai=\left(q_{j}p+r_{j}\right)-\left(q_{i}p+r_{i}\right)=\left(q_{j}-q_{i}\right)p.
\]

\end_inset

 С другой стороны 
\begin_inset Formula $aj-ai=a\left(j-i\right)$
\end_inset

, поэтому 
\begin_inset Formula 
\[
a\left(j-i\right)=\left(q_{j}-q_{i}\right)p.
\]

\end_inset


\end_layout

\begin_layout Proof
Но 
\begin_inset Formula $0<a<p$
\end_inset

 по условиям леммы, а 
\begin_inset Formula $0<j-i<p$
\end_inset

 так как 
\begin_inset Formula $0<j<p$
\end_inset

 и 
\begin_inset Formula $0<i<j$
\end_inset

.
 Таким образом, мы нашли два натуральных числа, меньших 
\begin_inset Formula $p$
\end_inset

, произведение которых делится на 
\begin_inset Formula $p$
\end_inset

.
 Но это невозможно в силу теоремы 5.4
\begin_inset Note Note
status open

\begin_layout Plain Layout
Добавить ссылку
\end_layout

\end_inset

.
\end_layout

\begin_layout Proof
Полученное противоречие означает, что совпадающих остатков нет, то есть
 все они различны.
\end_layout

\begin_layout Section
Сокращение
\end_layout

\begin_layout Standard
\begin_inset Note Note
status open

\begin_layout Plain Layout
Описать арифметику по модулю
\end_layout

\end_inset


\end_layout

\begin_layout Standard
Числа 
\begin_inset Formula $u$
\end_inset

 и 
\begin_inset Formula $v$
\end_inset

 являются взаимно обратимыми (по модулю 
\begin_inset Formula $n$
\end_inset

), если их произведение даёт остаток 1 при делении на 
\begin_inset Formula $n$
\end_inset

.
\end_layout

\begin_layout Lemma
(правило обратимости).
 Если 
\begin_inset Formula $p$
\end_inset

 простое, то для любого 
\begin_inset Formula $0<a<p$
\end_inset

 существует такое 
\begin_inset Formula $0<b<p$
\end_inset

, что 
\begin_inset Formula $ab=mp+1$
\end_inset

.
\end_layout

\begin_layout Proof
\begin_inset Note Comment
status open

\begin_layout Plain Layout
В книге 
\begin_inset Quotes rld
\end_inset

От математики к обобщённому программированию
\begin_inset Quotes rrd
\end_inset

 эта лемма доказывается через лемму о перестановке остатков.
 Можно поступить наоборот: доказать лемму 5.2 другим способом, а в теореме
 5.4 использовать эту лемму.
 Мы попробуем поступить именно так.
\end_layout

\end_inset


\end_layout

\begin_layout Standard
Рассмотрим всевозможные выражения вида 
\begin_inset Formula $sa+tp$
\end_inset

, где 
\begin_inset Formula $s$
\end_inset

 и 
\begin_inset Formula $t$
\end_inset

 — произвольные целые числа.
 Пусть 
\begin_inset Formula $d$
\end_inset

 — наименьшее положительное число, которое может быть представлено в таком
 виде.
 Докажем, что 
\begin_inset Formula $d=1$
\end_inset

.
 Пойдём от противного, пусть 
\begin_inset Formula $d>1$
\end_inset

.
 Разделим 
\begin_inset Formula $p$
\end_inset

 на 
\begin_inset Formula $d$
\end_inset

 с остатком, то есть запишем 
\begin_inset Formula $p$
\end_inset

 в виде 
\begin_inset Formula $p=qd+r$
\end_inset

, где 
\begin_inset Formula $0<r<d$
\end_inset

 (равенство 
\begin_inset Formula $r$
\end_inset

 нулю невозможно в силу того, что 
\begin_inset Formula $p$
\end_inset

 — простое, а значит делится без остатка только на 
\begin_inset Formula $1$
\end_inset

 и 
\begin_inset Formula $p$
\end_inset

).
 Тогда 
\begin_inset Formula 
\[
p=q\left(sa+tp\right)+r
\]

\end_inset

 или 
\begin_inset Formula 
\[
\left(1-t\right)p+\left(-sq\right)a=r,
\]

\end_inset

так как 
\begin_inset Formula $0<r<d$
\end_inset

, то мы пришли к противоречию с тем, что 
\begin_inset Formula $d$
\end_inset

 наименьшее из чисел, представимых в подобном виде.
\end_layout

\begin_layout Standard
Итак, мы показали, что существуют 
\begin_inset Formula $s$
\end_inset

 и 
\begin_inset Formula $t$
\end_inset

 такие, что 
\begin_inset Formula $sa+tp=1$
\end_inset

, положив 
\begin_inset Formula $b=s$
\end_inset

, получим 
\begin_inset Formula $ab=-tp+1$
\end_inset

, то есть требуемое равенство с 
\begin_inset Formula $m=-t$
\end_inset

.
\end_layout

\begin_layout Standard
Элементы 
\begin_inset Formula $1$
\end_inset

 и 
\begin_inset Formula $p-1$
\end_inset

 являются обратными к самим себе.
 Очевидно, что 
\begin_inset Formula $1\cdot1=1=0\cdot p+1$
\end_inset

.
 Аналогично:
\begin_inset Formula 
\[
\left(p-1\right)^{2}=p^{2}-p+1=\left(p-1\right)p+1.
\]

\end_inset


\end_layout

\begin_layout Standard
Более того, 
\begin_inset Formula $1$
\end_inset

 и 
\begin_inset Formula $p-1$
\end_inset

 — единственные самообратимые элементы.
\end_layout

\begin_layout Lemma
(правило самообратимы) Для любого 
\begin_inset Formula $0<a<p$
\end_inset

 из 
\begin_inset Formula $a^{2}=mp+1$
\end_inset

 следует, что 
\begin_inset Formula $a=1$
\end_inset

 или 
\begin_inset Formula $a=p-1$
\end_inset

.
\end_layout

\begin_layout Proof
Пусть 
\begin_inset Formula $a^{2}=mp+1$
\end_inset

, но 
\begin_inset Formula $a\neq1$
\end_inset

 и 
\begin_inset Formula $a\neq p-1$
\end_inset

.
 тогда 
\begin_inset Formula $a^{2}-1=mp$
\end_inset

 .
 По формуле разности квадратов
\begin_inset Formula 
\[
a^{2}-1=\left(a-1\right)\left(a+1\right).
\]

\end_inset

 То есть 
\begin_inset Formula $\left(a-1\right)\left(a+1\right)=mp$
\end_inset

 или 
\begin_inset Formula $\left(a-1\right)\left(a+1\right)$
\end_inset

 делится на 
\begin_inset Formula $p$
\end_inset

.
 Так как 
\begin_inset Formula $1<a<p-1$
\end_inset

, то 
\begin_inset Formula 
\[
0<a-1<p-2<p
\]

\end_inset

 и 
\begin_inset Formula 
\[
0<2<a+1<p.
\]

\end_inset


\end_layout

\begin_layout Proof
Но тогда 
\begin_inset Formula $a-1$
\end_inset

 и 
\begin_inset Formula $a+1$
\end_inset

 не делятся на 
\begin_inset Formula $p$
\end_inset

, а значит по теореме 5.4 
\begin_inset Note Note
status open

\begin_layout Plain Layout
Добавить ссылку
\end_layout

\end_inset

, 
\begin_inset Formula $\left(a-1\right)\left(a+1\right)$
\end_inset

 также не делится на 
\begin_inset Formula $p$
\end_inset

.
 Но выше мы видели, что 
\begin_inset Formula $\left(a-1\right)\left(a+1\right)$
\end_inset

 делится на 
\begin_inset Formula $p$
\end_inset

.
 Полученное противоречие показывает, что 
\begin_inset Formula $a=1$
\end_inset

 или 
\begin_inset Formula $a=p-1$
\end_inset

.
\end_layout

\begin_layout Theorem
(теорема Вильсона).
 Если 
\begin_inset Formula $p$
\end_inset

 простое, то существует такое целое 
\begin_inset Formula $m$
\end_inset

, что 
\begin_inset Formula 
\[
\left(p-1\right)!=mp+\left(p-1\right),
\]

\end_inset

или, иными словами: 
\begin_inset Formula 
\[
\left(p-1\right)!=\left(p-1\right)\mod p.
\]

\end_inset


\end_layout

\begin_layout Proof
\begin_inset Note Comment
status open

\begin_layout Plain Layout
Не смог догадаться сам, что нужно воспользоваться правилом самообратимости
\end_layout

\end_inset

 По определению 
\begin_inset Formula 
\[
\left(p-1\right)!=\prod_{k=1}^{p-1}k=1\cdot2\cdot3\cdot\dots\cdot\left(p-1\right).
\]

\end_inset


\end_layout

\begin_layout Proof
По правилу самообратимости
\begin_inset Note Note
status open

\begin_layout Plain Layout
Добавить ссылку
\end_layout

\end_inset

 все множители в правой части, кроме 
\begin_inset Formula $1$
\end_inset

 и 
\begin_inset Formula $p-1$
\end_inset

, разбиваются на пары обратных к друг другу по модулю 
\begin_inset Formula $p$
\end_inset

.
 Поэтому произведение 
\begin_inset Formula $2\cdot3\cdot\dots\cdot\left(p-2\right)$
\end_inset

 представимо в виде 
\begin_inset Formula $np+1$
\end_inset

, поэтому 
\begin_inset Formula 
\[
\left(p-1\right)!=\left(np+1\right)\left(p-1\right)=n\left(p-1\right)p+\left(p-1\right).
\]

\end_inset

 Полагая 
\begin_inset Formula $m=n\left(p-1\right)$
\end_inset

 получим требуемое равенство.
\end_layout

\begin_layout Problem
Докажите, что если 
\begin_inset Formula $n>4$
\end_inset

, то 
\begin_inset Formula $\left(n-1\right)!$
\end_inset

 кратно 4.
\end_layout

\begin_layout Solution
Если 
\begin_inset Formula $n>4$
\end_inset

, то 
\begin_inset Formula $\left(n-1\right)!=1\cdot2\cdot3\cdot4\cdot\dots\cdot(n-1)$
\end_inset

 то есть 
\begin_inset Formula $\left(n-1\right)!$
\end_inset

 содержит множитель 
\begin_inset Formula $4$
\end_inset

.
\end_layout

\begin_layout Section
Доказательство малой теоремы Ферма
\end_layout

\begin_layout Standard
Воспользовавшись полученными выше в этой главе результатами, можно доказать
 малую теорему Ферма.
\end_layout

\begin_layout Theorem*
\begin_inset Note Note
status open

\begin_layout Plain Layout
Добавить ссылку на эту же формулировку выше
\end_layout

\end_inset

Если 
\begin_inset Formula $p$
\end_inset

 простое, то 
\begin_inset Formula $a^{p-1}-1$
\end_inset

 делится на 
\begin_inset Formula $p$
\end_inset

 для любого 
\begin_inset Formula $0<a<p$
\end_inset

.
\end_layout

\begin_layout Proof
Рассмотрим выражение 
\begin_inset Formula 
\[
\prod_{k=1}^{p-1}\left(ak\right)=a^{p-1}\prod_{k=1}^{p-1}k=a^{p-1}\left(p-1\right)!.
\]

\end_inset


\end_layout

\begin_layout Proof
По теореме Вильсона 
\begin_inset Note Note
status open

\begin_layout Plain Layout
добавить ссылку
\end_layout

\end_inset


\begin_inset Formula $\left(p-1\right)!=mp+\left(p-1\right)$
\end_inset

, поэтому 
\begin_inset Formula 
\begin{multline*}
\prod_{k=1}^{p-1}\left(ak\right)=a^{p-1}\left(mp+\left(p-1\right)\right)=\\
=a^{p-1}\left(m+1\right)p-a^{p-1}=vp-a^{p-1},
\end{multline*}

\end_inset

где 
\begin_inset Formula $v$
\end_inset

 — некоторое целое число.
\end_layout

\begin_layout Proof
С другой стороны, любое произведение 
\begin_inset Formula $ak$
\end_inset

 можно разделить с остатком на 
\begin_inset Formula $p$
\end_inset

, то есть представить в виде 
\begin_inset Formula 
\[
ak=q_{k}p+r_{k},
\]

\end_inset

 где 
\begin_inset Formula $q_{k}$
\end_inset

 и 
\begin_inset Formula $r_{k}$
\end_inset

 — целые числа и 
\begin_inset Formula $0<r_{k}<p$
\end_inset

.
 Тогда 
\begin_inset Formula 
\[
\prod_{k=1}^{p-1}\left(ak\right)=\prod_{k=1}^{p-1}\left(q_{k}p+r_{k}\right).
\]

\end_inset


\end_layout

\begin_layout Proof
Раскрывая в этом произведении скобки получим 
\begin_inset Formula 
\[
\prod_{k=1}^{p-1}\left(ak\right)=up+\prod_{k=1}^{p-1}r_{k},
\]

\end_inset

 где 
\begin_inset Formula $u$
\end_inset

 — некоторое целое число.
 По лемме о перестановке остатков 
\begin_inset Note Note
status open

\begin_layout Plain Layout
добавить ссылку
\end_layout

\end_inset

 множество 
\begin_inset Formula $\left\{ r_{1},\dots,r_{p-1}\right\} $
\end_inset

 является перестановкой множества 
\begin_inset Formula $\left\{ 1,2,\dots,p-1\right\} $
\end_inset

, поэтому 
\begin_inset Formula 
\[
\prod_{k=1}^{p-1}r_{k}=\left(p-1\right)!,
\]

\end_inset

поэтому 
\begin_inset Formula 
\begin{multline*}
\prod_{k=1}^{p-1}\left(ak\right)=up+\left(p-1\right)!=up+mp+\left(p-1\right)=\\
=\left(u+m+1\right)p-1=wp-1,
\end{multline*}

\end_inset

где 
\begin_inset Formula $w=u+m+1$
\end_inset

.
 Приравнивания два выражения 
\begin_inset Note Note
status open

\begin_layout Plain Layout
добавить ссылки
\end_layout

\end_inset

 для 
\begin_inset Formula $\prod_{k=1}^{p-1}\left(ak\right)$
\end_inset

, получим 
\begin_inset Formula 
\[
wp-1=vp-a^{p-1}
\]

\end_inset

 или 
\begin_inset Formula 
\[
a^{p-1}-1=vp-wp=\left(v-w\right)p,
\]

\end_inset

 так как 
\begin_inset Formula $\left(v-w\right)$
\end_inset

 — целое число, то что 
\begin_inset Formula $a^{p-1}-1$
\end_inset

 делится на 
\begin_inset Formula $p$
\end_inset

, что и требовалось доказать.
\end_layout

\begin_layout Standard
Заметим, что 
\begin_inset Formula $a^{p-2}$
\end_inset

 является обратным к 
\begin_inset Formula $a$
\end_inset

, поэтому что 
\begin_inset Formula $a^{p-2}a=a^{p-1}$
\end_inset

, что, по малой теореме Ферма, равно 
\begin_inset Formula $mp+1$
\end_inset

.
\end_layout

\begin_layout Standard
Справедливо ли утверждение, обратное малой теореме Ферма.
 Для ответа на этот вопрос нужен ещё один промежуточный результат.
\end_layout

\begin_layout Lemma
(Лемма о необратимости).
 Если 
\begin_inset Formula $n=uv$
\end_inset

 и 
\begin_inset Formula $u,v>1$
\end_inset

, то 
\begin_inset Formula $u$
\end_inset

 не является обратимым по модулю 
\begin_inset Formula $n$
\end_inset

.
\end_layout

\begin_layout Proof
Нужно доказать, что не существует числа 
\begin_inset Formula $w$
\end_inset

 такого, что 
\begin_inset Formula $wu=1\mod n$
\end_inset

.
 Доказывать будем от противного.
 Пусть существует такое целое 
\begin_inset Formula $w$
\end_inset

, что 
\begin_inset Formula $wu=mn+1$
\end_inset

.
 Умножим это равенство на 
\begin_inset Formula $v$
\end_inset

: 
\begin_inset Formula 
\[
wuv=mnv+v,
\]

\end_inset

так как 
\begin_inset Formula $n=uv$
\end_inset

 по условию, то 
\begin_inset Formula 
\[
v=wn-mnv=\left(w-mv\right)n.
\]

\end_inset

Так как 
\begin_inset Formula $n=uv$
\end_inset

 и 
\begin_inset Formula $u>1$
\end_inset

, то 
\begin_inset Formula $v<n$
\end_inset

.
 Но это противоречит равенству 
\begin_inset Formula $v=\left(w-mv\right)n$
\end_inset

.
 Если 
\begin_inset Formula $z=w-mw>0$
\end_inset

, то 
\begin_inset Formula $zn\ge n>v$
\end_inset

.
 Если же 
\begin_inset Formula $z<0$
\end_inset

, то 
\begin_inset Formula $zn<0$
\end_inset

, но 
\begin_inset Formula $v>1$
\end_inset

 по условию.
\end_layout

\begin_layout Proof
Полученное противоречие означает, что предположение было неправильным и
 для 
\begin_inset Formula $u$
\end_inset

 не существует обратного элемента.
\end_layout

\begin_layout Definition
Числа 
\begin_inset Formula $m$
\end_inset

 и 
\begin_inset Formula $n$
\end_inset

 называются взаимно простыми, если 
\begin_inset Formula $\gcd\left(m,n\right)=1$
\end_inset

.
 Иначе говоря, 
\begin_inset Formula $m$
\end_inset

 и 
\begin_inset Formula $n$
\end_inset

 взаимно простые, если у них нет общих делителей, больших 
\begin_inset Formula $1$
\end_inset

.
\end_layout

\begin_layout Definition
По лемме о необратимости, в арифметике по модулю 
\begin_inset Formula $n$
\end_inset

, где число 
\begin_inset Formula $n$
\end_inset

 — не простое, бывают как обратимые, так и не обратимые элементы.
 Те элементы, которые не являются взаимно-простыми с 
\begin_inset Formula $n$
\end_inset

, необратимы.
\end_layout

\begin_layout Theorem
(обращение малой теоремы Ферма)
\end_layout

\begin_layout Theorem
Если для любого 
\begin_inset Formula $a$
\end_inset

 такого, что 
\begin_inset Formula $0<a<n$
\end_inset

 имеет место равенство 
\begin_inset Formula 
\[
a^{n-1}=1+q_{a}n,
\]

\end_inset

то 
\begin_inset Formula $n$
\end_inset

 простое.
\end_layout

\begin_layout Proof
\begin_inset Note Comment
status open

\begin_layout Plain Layout
Не додумался до этого шага сам
\end_layout

\end_inset

 Допустим, что 
\begin_inset Formula $n=uv$
\end_inset

 — не простое число.
 Тогда, по лемме о необратимости 
\begin_inset Note Note
status open

\begin_layout Plain Layout
добавить ссылку
\end_layout

\end_inset

, число 
\begin_inset Formula $u$
\end_inset

 является необратимым.
 Но по условию теоремы 
\begin_inset Formula 
\[
u^{n-1}=u^{n-2}\cdot u=1+q_{u}n,
\]

\end_inset

то есть 
\begin_inset Formula $u$
\end_inset

 и 
\begin_inset Formula $u^{n-2}$
\end_inset

 являются взаимно обратными элементами или, иными словами, число 
\begin_inset Formula $u$
\end_inset

 — обратимо по модулю 
\begin_inset Formula $n$
\end_inset

.
 Полученное противоречие означает, что исходное предположение было неправильным
 и 
\begin_inset Formula $n$
\end_inset

 — простое число.
\end_layout

\begin_layout Section
Теорема Эйлера
\end_layout

\begin_layout Definition
Функцией Эйлера 
\begin_inset Formula $\phi\left(n\right)$
\end_inset

 целого положительного числа 
\begin_inset Formula $n$
\end_inset

 называется количество целых положительных чисел, меньших 
\begin_inset Formula $n$
\end_inset

 и взаимно простых с 
\begin_inset Formula $n$
\end_inset

.
\end_layout

\begin_layout Standard
Поскольку у простого числа 
\begin_inset Formula $p$
\end_inset

 по определению нет простых общих делителей с меньшими числами, то 
\begin_inset Formula $\phi\left(p\right)=p-1$
\end_inset

.
\end_layout

\begin_layout Standard
Эйлер понял, что показатель степени 
\begin_inset Formula $p-1$
\end_inset

 в малой теореме Ферма — просто частный случай, а именно значение функции
 
\begin_inset Formula $\phi$
\end_inset

 для простых чисел.
 А обобщение Эйлера этой теоремы формулируется следующим образом.
\end_layout

\begin_layout Theorem
(Теорема Эйлера).
 Если 
\begin_inset Formula $a$
\end_inset

 и 
\begin_inset Formula $n$
\end_inset

 взаимно просты, то 
\begin_inset Formula $a^{\phi\left(n\right)}-1$
\end_inset

 делится на 
\begin_inset Formula $n$
\end_inset

.
\end_layout

\begin_layout Problem
Докажите теорему Эйлера, модифицировав доказательство малой теоремы Ферма.
 Вот перечень необходимых шагов:
\end_layout

\begin_layout Problem
1) Заменить лемму о перестановке остатков леммой о перестановке взаимно-простых
 остатков.
\end_layout

\begin_layout Problem
2) Доказать, что у каждого взаимно простого остатка есть обратный элемент
 относительно умножения по модулю (на предыдущем шаге было показано, что
 такие остатки образуют перестановку, поэтому 1 должна встречаться только
 в перестановке).
\end_layout

\begin_layout Problem
3) Использовать произведение всех взаимно простых остатков там где в доказательс
тве малой теоремы Ферма фигурирует произведение всех ненулевых остатков.
\end_layout

\begin_layout Exercise*
\begin_inset Note Note
status open

\begin_layout Plain Layout
Написать решение
\end_layout

\end_inset


\end_layout

\begin_layout Exercise*
Пусть 
\begin_inset Formula $1=b_{1},\dots,b_{m}$
\end_inset

 — все остатки, взаимно простые с 
\begin_inset Formula $n$
\end_inset

 (
\begin_inset Formula $b_{1}=1$
\end_inset

, так как любое число являются взаимно простым с 
\begin_inset Formula $1$
\end_inset

).
 Будем считать, что они упорядочены по возрастанию.
 Тогда 
\begin_inset Formula $m=\phi\left(n\right)$
\end_inset

.
\end_layout

\begin_layout Exercise*
1) Рассмотрим произведения 
\begin_inset Formula $ab_{j}$
\end_inset

 по модулю 
\begin_inset Formula $n$
\end_inset

:
\begin_inset Formula 
\[
ab_{j}=q_{j}n+r_{j},j=1,\dots,\phi\left(n\right).
\]

\end_inset

 Докажем, множество 
\begin_inset Formula $\left\{ r_{1},\dots,r_{m}\right\} $
\end_inset

 является перестановкой множества 
\begin_inset Formula $\left\{ b_{1},\dots,b_{m}\right\} $
\end_inset

.
 
\end_layout

\begin_layout Exercise*
Начнём с того, что докажем, что все 
\begin_inset Formula $ab_{j}$
\end_inset

 различны.
 Пойдём от противного, пусть 
\begin_inset Formula $r_{j}=r_{k}$
\end_inset

 и 
\begin_inset Formula $k>j$
\end_inset

, тогда 
\begin_inset Formula 
\[
ab_{k}-ab_{j}=\left(q_{k}-q_{j}\right)n+\left(r_{k}-r_{j}\right)=\left(q_{k}-q_{j}\right)n,
\]

\end_inset

с другой стороны 
\begin_inset Formula 
\[
ab_{k}-ab_{j}=a\left(b_{k}-b_{j}\right),
\]

\end_inset

поэтому 
\begin_inset Formula 
\[
a\left(b_{k}-b_{j}\right)=\left(q_{k}-q_{j}\right)n.
\]

\end_inset


\end_layout

\begin_layout Exercise*
Числа 
\begin_inset Formula $a$
\end_inset

 и 
\begin_inset Formula $n$
\end_inset

 взаимно просты по условию, поэтому 
\begin_inset Formula $b_{k}-b_{j}$
\end_inset

 должно делиться на 
\begin_inset Formula $n$
\end_inset

.
 Но 
\begin_inset Formula $0<b_{k}-b_{j}<n$
\end_inset

, полученное противоречие означает, что 
\begin_inset Formula $r_{j}\neq r_{k}$
\end_inset

 при 
\begin_inset Formula $j\neq k$
\end_inset

.
\end_layout

\begin_layout Exercise*
Теперь нужно доказать, что остатки 
\begin_inset Formula $r_{j}$
\end_inset

 являются взаимно простыми с 
\begin_inset Formula $n$
\end_inset

.
 По определению, 
\begin_inset Formula $ab_{j}=q_{j}n+r_{j}$
\end_inset

.
 Пусть у 
\begin_inset Formula $r_{j}$
\end_inset

 и 
\begin_inset Formula $n$
\end_inset

 есть простой общий делитель 
\begin_inset Formula $d>1$
\end_inset

, тогда 
\begin_inset Formula $ab_{j}$
\end_inset

 также должно делиться на 
\begin_inset Formula $d$
\end_inset

.
 Но 
\begin_inset Formula $a$
\end_inset

 и 
\begin_inset Formula $b_{j}$
\end_inset

 не делятся на 
\begin_inset Formula $d$
\end_inset

, так как у них нет общих делителей с 
\begin_inset Formula $n$
\end_inset

 (у 
\begin_inset Formula $a$
\end_inset

 — по условию, а у 
\begin_inset Formula $b_{j}$
\end_inset

 по определению).
\end_layout

\begin_layout Exercise*
Таким образом, множество 
\begin_inset Formula $\left\{ r_{1},\dots r_{m}\right\} $
\end_inset

 содержит ровно 
\begin_inset Formula $m$
\end_inset

 различных элементов, каждый из которых должен совпадать с одним из 
\begin_inset Formula $\left\{ b_{1},\dots,b_{m}\right\} $
\end_inset

, то есть эти множества являются перестановками друг друга.
\end_layout

\begin_layout Exercise*
2) Докажем теперь, что у каждого элемента множества взаимно простых остатков
 
\begin_inset Formula $\left\{ b_{1},\dots,b_{m}\right\} $
\end_inset

 есть обратный элемент относительно умножения по модулю 
\begin_inset Formula $n$
\end_inset

.
 Пусть мы рассматриваем элемент 
\begin_inset Formula $b_{j}$
\end_inset

.
 Применив пункт 1) к 
\begin_inset Formula $a=b_{j}$
\end_inset

, мы получим, что среди 
\begin_inset Formula $b_{j}b_{k}$
\end_inset

 при 
\begin_inset Formula $k=1,\dots,m$
\end_inset

 есть 
\begin_inset Formula $b_{1}=1$
\end_inset

, соответствующий 
\begin_inset Formula $b_{k}$
\end_inset

 и будет элементом, обратным к 
\begin_inset Formula $b_{j}$
\end_inset

.
\end_layout

\begin_layout Exercise*
3) Рассмотрим произведение 
\begin_inset Formula 
\[
\prod_{j=1}^{m}\left(ab_{j}\right)=a^{m}\prod_{j=1}^{m}b_{j}.
\]

\end_inset

 Так как множество 
\begin_inset Formula $\left\{ ab_{1}\mod n,\dots ab_{m}\mod n\right\} $
\end_inset

 является перестановкой множества 
\begin_inset Formula $\left\{ b_{1},\dots,b_{m}\right\} $
\end_inset

, то 
\begin_inset Formula 
\[
\prod_{j=1}^{m}\left(ab_{j}\right)=\prod_{j=1}^{m}b_{j}+un,
\]

\end_inset

где 
\begin_inset Formula $u$
\end_inset

 — некоторое целое число.
 Таким образом 
\begin_inset Formula 
\[
a^{m}\prod_{j=1}^{m}b_{j}-\prod_{j=1}^{m}b_{j}=\left(a^{m}-1\right)\prod_{j=1}^{m}b_{j}=un.
\]

\end_inset


\end_layout

\begin_layout Exercise*
\begin_inset Note Note
status open

\begin_layout Plain Layout
Может быть через аналог теоремы Вильсона?
\end_layout

\end_inset


\end_layout

\begin_layout Exercise*
Так как все 
\begin_inset Formula $b_{j}$
\end_inset

 не имеют общих множителей с 
\begin_inset Formula $n$
\end_inset

, то и у их произведения нет общих множителей с 
\begin_inset Formula $n$
\end_inset

, поэтому 
\begin_inset Formula 
\[
a^{m}-1=a^{\phi\left(n\right)}-1
\]

\end_inset

 делится на 
\begin_inset Formula $n$
\end_inset

, что и требовалось доказать.
\end_layout

\begin_layout Standard
\begin_inset Note Note
status open

\begin_layout Plain Layout
Написать про вычисление функции Эйлера по разложению числа на простые множители
\end_layout

\end_inset


\end_layout

\begin_layout Standard
Пусть для целого положительного числа 
\begin_inset Formula $n$
\end_inset

 задано его разложение на простые множители 
\begin_inset Formula $n=p_{1}^{k_{1}}\cdot\dots p_{m}^{k_{m}}$
\end_inset

.
 Вычислим для него функцию Эйлера.
 Будем постепенно рассматривать всё более сложные случаи.
\end_layout

\begin_layout Standard
Пусть сначала 
\begin_inset Formula $m=1$
\end_inset

 и 
\begin_inset Formula $k_{1}=1$
\end_inset

, тогда 
\begin_inset Formula $\phi\left(n\right)=\phi\left(p_{1}\right)=p_{1}-1$
\end_inset

, так как любое простое число является взаимно простым со всеми целыми положител
ьными числами, меньшими его.
\end_layout

\begin_layout Standard
Пусть теперь 
\begin_inset Formula $n=p^{k}$
\end_inset

, где 
\begin_inset Formula $k\ge1$
\end_inset

 — целое число.
 Тогда у 
\begin_inset Formula $n$
\end_inset

 и любого целого положительного, кратного 
\begin_inset Formula $p$
\end_inset

, есть общий множитель.
 Таких чисел в интервале 
\begin_inset Formula $\left[1,n-1\right]$
\end_inset

 имеется 
\begin_inset Formula $\frac{n}{p}-1$
\end_inset

, поэтому 
\begin_inset Formula 
\begin{multline*}
\phi\left(n\right)=\left(n-1\right)-\frac{n}{p}-1=\\
=n-\frac{n}{p}=p^{k}-p^{k-1}=p^{k}\left(1-\frac{1}{p}\right).
\end{multline*}

\end_inset


\end_layout

\begin_layout Standard
Пусть теперь 
\begin_inset Formula $n=p_{1}^{k_{1}}p_{2}^{k_{2}}$
\end_inset

.
 Тогда у 
\begin_inset Formula $n$
\end_inset

 имеются общие делители с любыми числами, кратными 
\begin_inset Formula $p_{1}$
\end_inset

 или 
\begin_inset Formula $p_{2}$
\end_inset

.
 Таких чисел, среди 
\begin_inset Formula $\left[1;n-1\right]$
\end_inset

 имеется 
\begin_inset Formula $\frac{n-p_{1}}{p_{1}}+\frac{n-p_{2}}{p_{2}}-\frac{n-p_{1}p_{2}}{p_{1}p_{2}}$
\end_inset

 (мы вычли количество чисел, кратных 
\begin_inset Formula $p_{1}p_{2}$
\end_inset

, иначе эти числа были бы учтены два раза, это называется принципом влюкчения-ис
ключения
\begin_inset Note Note
status open

\begin_layout Plain Layout
написать про него отдельно
\end_layout

\end_inset

).
 Таким образом 
\begin_inset Formula 
\begin{multline*}
\phi\left(n\right)=\left(n-1\right)-\left(\frac{n}{p_{1}}-1\right)-\left(\frac{n}{p_{2}}-1\right)+\frac{n}{p_{1}p_{2}}-1=\\
=n\left(1-\frac{1}{p_{1}}-\frac{1}{p_{2}}+\frac{1}{p_{1}p_{2}}\right)=n\left(1-\frac{1}{p_{1}}-\frac{1}{p_{2}}\left(1-\frac{1}{p_{1}}\right)\right)=\\
=n\left(1-\frac{1}{p_{1}}\right)\left(1-\frac{1}{p_{2}}\right)=p_{1}^{k_{1}}\left(1-\frac{1}{p_{1}}\right)p_{2}^{k_{2}}\left(1-\frac{1}{p_{2}}\right)=\\
=\phi\left(p_{1}^{k_{1}}\right)\phi\left(p_{2}^{k_{2}}\right).
\end{multline*}

\end_inset


\end_layout

\begin_layout Standard
\begin_inset Note Note
status open

\begin_layout Plain Layout
Доказать мультипликативность функции Эйлера
\end_layout

\end_inset


\end_layout

\begin_layout Chapter
Абстракция в математике
\end_layout

\begin_layout Section
Группы
\end_layout

\begin_layout Definition
Группой называется множество 
\begin_inset Formula $G$
\end_inset

, на котором определены операции 
\begin_inset Formula $x\circ y$
\end_inset

 и 
\begin_inset Formula $x^{-1}$
\end_inset

, а также константа 
\begin_inset Formula $e$
\end_inset

, таким образом, что
\end_layout

\begin_layout Definition
1) 
\begin_inset Formula $x\circ\left(y\circ z\right)=\left(x\circ y\right)\circ z$
\end_inset

 (ассоциативность)
\end_layout

\begin_layout Definition
2) 
\begin_inset Formula $x\circ e=e\circ x=x$
\end_inset

 (нейтральность)
\end_layout

\begin_layout Definition
3) 
\begin_inset Formula $x\circ x^{-1}=x^{-1}\circ x=e$
\end_inset

 (сокращение)
\end_layout

\begin_layout Standard
\begin_inset Separator plain
\end_inset


\end_layout

\begin_layout Definition
Абелевой называется группа, в которой операция 
\begin_inset Formula $\circ$
\end_inset

 коммутативна.
\end_layout

\begin_layout Standard
\begin_inset Separator plain
\end_inset


\end_layout

\begin_layout Definition
Аддитивной группой называется абелева группа, в которой операцией является
 сложение.
\end_layout

\begin_layout Problem
Для скольких целых чисел обращение относительно умножения также является
 целым? Что это за числа?
\end_layout

\begin_layout Solution
У целого числа 
\begin_inset Formula $0$
\end_inset

 не может быть обратного элемента, так как 
\begin_inset Formula $n\cdot0=0\neq1$
\end_inset

.
 Если 
\begin_inset Formula $n=\pm1$
\end_inset

, то 
\begin_inset Formula $n^{2}=\left(\pm1\right)^{2}=1$
\end_inset

, то есть числа 
\begin_inset Formula $\pm1$
\end_inset

 являются обратными для самих себя.
 Для остальных целых чисел выполняется 
\begin_inset Formula $\left|n\right|>1$
\end_inset

.
 Ноль не может быть обратным элементом ни для какого числа, так как 
\begin_inset Formula $n\cdot0=0\neq1$
\end_inset

.
 Для любого ненулевого целого числа 
\begin_inset Formula $m$
\end_inset

 выполняется 
\begin_inset Formula $\left|m\right|\ge1$
\end_inset

, поэтому 
\begin_inset Formula $\left|mn\right|>\left|m\right|\ge1$
\end_inset

.
 То есть у целого числа 
\begin_inset Formula $n$
\end_inset

, кроме 
\begin_inset Formula $\pm1$
\end_inset

, не может быть целого обратного элемента относительно умножения.
\end_layout

\begin_layout Solution
\begin_inset Note Note
status open

\begin_layout Plain Layout
Пример: остатки от деления на простое число образуют группу с операцией
 умножения
\end_layout

\end_inset


\end_layout

\begin_layout Section
Моноиды и полугруппы
\end_layout

\begin_layout Standard
Иногда интерес представляют алгебраические структуры, к которым предъявляется
 меньше требований, чем к группам.
 Например, не всегда нужна операция обращения, но другие свойства группы
 хотелось бы сохранить.
\end_layout

\begin_layout Definition
Моноидом называется множество, на котором определены операция 
\begin_inset Formula $\circ$
\end_inset

 и константа 
\begin_inset Formula $e$
\end_inset

 таким образом, что выполняются следующие аксиомы:
\end_layout

\begin_layout Definition
1) 
\begin_inset Formula $x\circ\left(y\circ z\right)=\left(x\circ y\right)\circ z$
\end_inset

 (ассоциативность)
\end_layout

\begin_layout Definition
2) 
\begin_inset Formula $x\circ e=e\circ x=x$
\end_inset

 (нейтральность)
\end_layout

\begin_layout Standard
Примеры моноидов: моноид конечных строк (свободный моноид), в нём операцией
 является конкатенация, а нейтральным элементом — пустая строка; мультипликативн
ый моноид целых чисел.
\end_layout

\begin_layout Definition
Полугруппой называется множество, на котором определена ассоциативная операция
 
\begin_inset Formula $\circ$
\end_inset

.
\end_layout

\begin_layout Definition
Повторное умножение нескольких одинаковых элементов, так же как и для умножения
 чисел, называется степенью.
\end_layout

\begin_layout Definition
\begin_inset Formula 
\[
x^{n}=\begin{cases}
x, & n=1,\\
x\circ x^{n-1}, & n>1.
\end{cases}
\]

\end_inset


\end_layout

\begin_layout Problem
Почему нельзя определить степень в полугруппе, начав с 
\begin_inset Formula $n=0$
\end_inset

?
\end_layout

\begin_layout Solution
Если мы хотим сохранить равенство 
\begin_inset Formula $x^{n+m}=x^{n}\circ x^{m}$
\end_inset

, то при 
\begin_inset Formula $m=0$
\end_inset

 должно быть 
\begin_inset Formula $x^{n}=x^{n}\circ x^{0}$
\end_inset

, то есть 
\begin_inset Formula $x^{0}=e$
\end_inset

, но в полугруппе нейтрального элемента может и не быть.
\end_layout

\begin_layout Standard
Мы определили степень так, что групповая операция применяется с степени
 с более низким показателем слева.
 Что измениться, если применить умножение с другой стороны? Оказывается,
 что при этом ничего не изменится.
\end_layout

\begin_layout Lemma
Для 
\begin_inset Formula $n\ge2$
\end_inset

 и ассоциативной операции 
\begin_inset Formula $\circ$
\end_inset

 выполняется равенство 
\begin_inset Formula $x\circ x^{n-1}=x^{n-1}\circ x$
\end_inset

.
\end_layout

\begin_layout Proof
Докажем это равенство по индукции.
 При 
\begin_inset Formula $n=2$
\end_inset

 получим равенство 
\begin_inset Formula $x\circ x=x\circ x$
\end_inset

, которое, очевидно, верно.
\end_layout

\begin_layout Proof
Пусть теперь мы доказали требуемое равенство для 
\begin_inset Formula $n=2,\dots,k$
\end_inset

.
 Докажем его для 
\begin_inset Formula $n=k+1$
\end_inset

.
 
\begin_inset Formula 
\begin{multline*}
x\circ x^{\left(k+1\right)-1}=x\circ x^{k}=x\circ\left(x^{k-1}\circ x\right)=\\
=\left(x\circ x^{k-1}\right)\circ x=\left(x^{k-1}\circ x\right)\circ x=\\
=x^{k}\circ x=x^{\left(k+1\right)-1}\circ x.
\end{multline*}

\end_inset


\end_layout

\begin_layout Standard
Более того, хотя вообще говоря умножение в полугруппе не является коммутативным,
 степени любого элемента коммутируют.
\end_layout

\begin_layout Theorem
(Коммутативность степеней) Пусть 
\begin_inset Formula $\circ$
\end_inset

 — ассоциативная операция, тогда 
\begin_inset Formula $x^{n}\circ x^{m}=x^{m}\circ x^{n}=x^{n+m}$
\end_inset

.
\end_layout

\begin_layout Proof
Доказательство проведём по индукции по 
\begin_inset Formula $m$
\end_inset

.
 При 
\begin_inset Formula $m=1$
\end_inset

 получаем утверждение леммы 6.1.
 
\begin_inset Note Note
status open

\begin_layout Plain Layout
Добавить ссылку
\end_layout

\end_inset


\end_layout

\begin_layout Proof
Пусть теперь мы доказали, что равенство выполняется для всех 
\begin_inset Formula $m=1,\dots,k$
\end_inset

.
 Докажем его для 
\begin_inset Formula $m=k+1$
\end_inset

.
 По определению степени 
\begin_inset Formula $x^{k+1}=x\circ x^{k}=x^{k}\circ x$
\end_inset

, тогда, в силу ассоциативности операции:
\begin_inset Formula 
\[
x^{n}\circ x^{k+1}=x^{n}\circ\left(x^{k}\circ x\right)=\left(x^{n}\circ x^{k}\right)\circ x.
\]

\end_inset

Так как требуемое равенство доказано для 
\begin_inset Formula $m=k$
\end_inset

, то 
\begin_inset Formula 
\[
x^{n}\circ x^{k+1}=x^{n+k}\circ x,
\]

\end_inset

а в силу леммы 6.1
\begin_inset Note Note
status open

\begin_layout Plain Layout
Добавить ссылку
\end_layout

\end_inset

: 
\begin_inset Formula 
\[
x^{n}\circ x^{k+1}=x^{n+k}\circ x=x^{n+k+1}.
\]

\end_inset


\end_layout

\begin_layout Proof
Мы показали, что 
\begin_inset Formula $x^{n}\circ x^{m}=x^{n+m}$
\end_inset

.
 Так как сложение целых чисел коммутативно, то 
\begin_inset Formula 
\[
x^{m}\circ x^{n}=x^{m+n}=x^{n+m},
\]

\end_inset

поэтому 
\begin_inset Formula 
\[
x^{n}\circ x^{m}=x^{m}\circ x^{n}=x^{n+m}.
\]

\end_inset


\end_layout

\begin_layout Standard
Полугруппа — самая слабая из интересных алгебраических структур.
 Единственное требование, которое ещё можно ослабить — аксиома ассоциативности.
 Если опустить её, получится алгебраическая структура, называемая 
\emph on
магмой
\emph default
, но на слишком полезна.
 Поскольку не осталось никаких аксиом, то нельзя доказать никаких теорем.
\end_layout

\begin_layout Section
Некоторые теоремы о группах
\end_layout

\begin_layout Standard
Важное наблюдение заключается в том, что группы являются группами преобразований.
 Другие словами, каждый элемент 
\begin_inset Formula $a$
\end_inset

 группы 
\begin_inset Formula $G$
\end_inset

 определяется преобразование 
\begin_inset Formula $G$
\end_inset

 на себя: 
\begin_inset Formula 
\[
x\mapsto ax.
\]

\end_inset


\end_layout

\begin_layout Theorem
Преобразование группы — взаимно однозначное соответствие.
\end_layout

\begin_layout Proof
Нужно доказать, что если 
\begin_inset Formula $ax=ay$
\end_inset

, то 
\begin_inset Formula $x=y$
\end_inset

.
 Действительно, так как у любого элемента группы, в том числе и у 
\begin_inset Formula $a$
\end_inset

, существует обратный элемент.
 Умножим равенство 
\begin_inset Formula $ax=ay$
\end_inset

 слева на 
\begin_inset Formula $a^{-1}$
\end_inset

, получим 
\begin_inset Formula 
\[
a^{-1}\left(ax\right)=a^{-1}\left(ay\right),
\]

\end_inset

 а так как умножение в группе ассоциативно, то 
\begin_inset Formula 
\[
a^{-1}\left(ax\right)=\left(a^{-1}a\right)x=ex=x,
\]

\end_inset

аналогично 
\begin_inset Formula $a^{-1}\left(ay\right)=y$
\end_inset

, поэтому 
\begin_inset Formula $x=y$
\end_inset

.
\end_layout

\begin_layout Standard
Иными словами, для любого конечного множества 
\begin_inset Formula $S$
\end_inset

 элементов группы 
\begin_inset Formula $G$
\end_inset

 и любого 
\begin_inset Formula $a\in G$
\end_inset

, в множестве 
\begin_inset Formula $aS$
\end_inset

 столько же элементов, сколько в 
\begin_inset Formula $S$
\end_inset

.
\end_layout

\begin_layout Theorem
Для каждого элемента группы существует только один обратный элемент.
\end_layout

\begin_layout Proof
Рассмотрим произвольную группы 
\begin_inset Formula $G$
\end_inset

 и её произвольный элемент 
\begin_inset Formula $a$
\end_inset

.
 Предположим, что в группе 
\begin_inset Formula $G$
\end_inset

 у элемента 
\begin_inset Formula $a$
\end_inset

 два обратных элемента 
\begin_inset Formula $b_{1}$
\end_inset

 и 
\begin_inset Formula $b_{2}$
\end_inset

.
 Рассмотрим произведение 
\begin_inset Formula $b_{1}ab_{2}$
\end_inset

.
 У этого выражения есть два способа вычисления, которые, в силу ассоциативности
 умножения, дают один и тот же результат: 
\begin_inset Formula 
\[
\left(b_{1}a\right)b_{2}=b_{1}\left(ab_{2}\right).
\]

\end_inset


\end_layout

\begin_layout Proof
Так как 
\begin_inset Formula $b_{1}$
\end_inset

 и 
\begin_inset Formula $b_{2}$
\end_inset

 — обратные элементы для 
\begin_inset Formula $a$
\end_inset

, то 
\begin_inset Formula $b_{1}a=ab_{2}=e$
\end_inset

.
 Таким образом, 
\begin_inset Formula 
\[
\left(b_{1}a\right)b_{2}=eb_{2}=b_{2},
\]

\end_inset


\begin_inset Formula 
\[
b_{1}\left(ab_{2}\right)=b_{1}e=b_{1}.
\]

\end_inset

 Так как левые части этих двух равенств равны, то равны и правые, поэтому
 
\begin_inset Formula 
\[
b_{1}=b_{2},
\]

\end_inset

 то есть у каждого элемента может быть только один обратный элемент.
\end_layout

\begin_layout Theorem
Элемент обратный произведению двух элементов, равен произведению обратных
 элементов в обратном порядке: 
\begin_inset Formula 
\[
\left(ab\right)^{-1}=b^{-1}a^{-1}.
\]

\end_inset


\end_layout

\begin_layout Proof
Так как выше мы показали 
\begin_inset Note Note
status open

\begin_layout Plain Layout
Добавить ссылку
\end_layout

\end_inset

, что обратный элемент является единственным, то достаточно показать, что
 
\begin_inset Formula $\left(b^{-1}a^{-1}\right)\left(ab\right)=\left(ab\right)\left(b^{-1}a^{-1}\right)=e$
\end_inset

.
 Действительно, так как умножение ассоциативно, то 
\begin_inset Formula 
\begin{multline*}
\left(b^{-1}a^{-1}\right)\left(ab\right)=b^{-1}\left(a^{-1}\left(ab\right)\right)=b^{-1}\left(\left(a^{-1}a\right)b\right)=\\
=b^{-1}\left(eb\right)=b^{-1}b=e.
\end{multline*}

\end_inset


\end_layout

\begin_layout Proof
Аналогично, 
\begin_inset Formula 
\begin{multline*}
\left(ab\right)\left(b^{-1}a^{-1}\right)=a\left(b\left(b^{-1}a^{-1}\right)\right)=a\left(\left(bb^{-1}\right)a^{-1}\right)=\\
=a\left(ea^{-1}\right)=aa^{-1}=e.
\end{multline*}

\end_inset


\end_layout

\begin_layout Theorem
Степень обратного элемента равна элементу, обратному степени: 
\begin_inset Formula 
\[
\left(x^{-1}\right)^{n}=\left(x^{n}\right)^{-1}.
\]

\end_inset


\end_layout

\begin_layout Proof
Так как выше мы показали 
\begin_inset Note Note
status open

\begin_layout Plain Layout
Добавить ссылку
\end_layout

\end_inset

, что обратный элемент является единственным, то достаточно показать, что
 
\begin_inset Formula $x^{n}\left(x^{-1}\right)^{n}=\left(x^{-1}\right)^{n}x^{n}=e$
\end_inset

.
 Доказательство проведём по индукции.
\end_layout

\begin_layout Proof
При 
\begin_inset Formula $n=1$
\end_inset

 равенство тривиально: 
\begin_inset Formula $x^{-1}=x^{-1}$
\end_inset

.
\end_layout

\begin_layout Proof
Пусть равенство доказано для всех 
\begin_inset Formula $n=1,\dots,k$
\end_inset

.
 Докажем, его для 
\begin_inset Formula $x^{k+1}$
\end_inset

.
 По определению степени 
\begin_inset Formula 
\begin{multline*}
x^{k+1}\left(x^{-1}\right)^{k+1}=\left[x^{k}x\right]\left[x^{-1}\left(x^{-1}\right)^{k}\right]=\\
=x^{k}\left[xx^{-1}\right]\left(x^{-1}\right)^{k}=x^{k}\left(x^{-1}\right)^{k}=e,
\end{multline*}

\end_inset

 аналогично:
\begin_inset Formula 
\[
\left(x^{-1}\right)^{k+1}x^{k+1}=\left(x^{-1}\right)^{k}x^{-1}xx^{k}=\left(x^{-1}\right)^{k}x^{k}=e.
\]

\end_inset


\end_layout

\begin_layout Proof
Таким образом, равенство 
\begin_inset Formula $\left(x^{-1}\right)^{n}=\left(x^{n}\right)^{-1}$
\end_inset

 справедливо для всех натуральных 
\begin_inset Formula $n$
\end_inset

.
\end_layout

\begin_layout Problem
Докажите, что в любой группе есть хотя бы один элемент.
\end_layout

\begin_layout Solution
В любой группе есть нейтральный элемент 
\begin_inset Formula $e$
\end_inset

.
\end_layout

\begin_layout Definition
Если группа состоит из 
\begin_inset Formula $n>0$
\end_inset

 элементов, то 
\begin_inset Formula $n$
\end_inset

 называют порядком группы.
 Если в группе бесконечно много элементов, то её порядок бесконечен.
\end_layout

\begin_layout Standard
\begin_inset Separator plain
\end_inset


\end_layout

\begin_layout Definition
Говорят, что элемент 
\begin_inset Formula $a$
\end_inset

 имеет порядок 
\begin_inset Formula $n>0$
\end_inset

, если 
\begin_inset Formula $a^{n}=e$
\end_inset

 и для любого 
\begin_inset Formula $0<k<n$
\end_inset

 имеет место 
\begin_inset Formula $a^{k}\neq e$
\end_inset

 (иными словами, порядок 
\begin_inset Formula $a$
\end_inset

 — это наименьшая степень, при возведении в которую получается нейтральный
 элемент 
\begin_inset Formula $e$
\end_inset

).
 Если такого 
\begin_inset Formula $n$
\end_inset

 не существует, то говорят, что порядок 
\begin_inset Formula $a$
\end_inset

 бесконечен.
\end_layout

\begin_layout Problem
Чему равен порядок 
\begin_inset Formula $e$
\end_inset

? Докажите, что 
\begin_inset Formula $e$
\end_inset

 — единственный элемент, имеющий такой порядок.
\end_layout

\begin_layout Solution
Так как 
\begin_inset Formula $e^{1}=e$
\end_inset

, то порядок 
\begin_inset Formula $e$
\end_inset

 равен 
\begin_inset Formula $1$
\end_inset

.
 Пусть теперь порядок элемента 
\begin_inset Formula $a$
\end_inset

 равен 
\begin_inset Formula $1$
\end_inset

, значит 
\begin_inset Formula $a=a^{1}=e$
\end_inset

, то есть 
\begin_inset Formula $e$
\end_inset

 — единственный элемент, порядок которого равен 
\begin_inset Formula $1$
\end_inset

.
\end_layout

\begin_layout Theorem
Каждый элемент конечной группы имеет конечный порядок.
\end_layout

\begin_layout Solution
Пусть 
\begin_inset Formula $G$
\end_inset

 — группа конечного порядка 
\begin_inset Formula $n$
\end_inset

, а 
\begin_inset Formula $a$
\end_inset

 — элемент этой группы, причём его порядок бесконечен, то есть для любого
 натурального 
\begin_inset Formula $k$
\end_inset

 выполняется 
\begin_inset Formula $a^{k}\neq e$
\end_inset

.
 Тогда все степени элемента 
\begin_inset Formula $a$
\end_inset

 различны.
 Действительно, пусть 
\begin_inset Formula $j>i$
\end_inset

 и 
\begin_inset Formula $a^{j}=a^{i}$
\end_inset

.
 Умножим это равенство на 
\begin_inset Formula $\left(a^{i}\right)^{-1}$
\end_inset

.
 По теореме 6.5
\begin_inset Note Note
status open

\begin_layout Plain Layout
добавить ссылку
\end_layout

\end_inset

 
\begin_inset Formula $\left(a^{i}\right)^{-1}=\left(a^{-1}\right)^{i}$
\end_inset

, поэтому 
\begin_inset Formula 
\[
a^{j}\left(a^{-1}\right)^{i}=a^{i}\left(a^{i}\right)^{-1}=e.
\]

\end_inset


\end_layout

\begin_layout Solution
Таким образом, 
\begin_inset Formula $a^{j-i}=e$
\end_inset

, то есть 
\begin_inset Formula $a$
\end_inset

 — элемент порядка не выше 
\begin_inset Formula $j-i$
\end_inset

, но это противоречит тому, что для любого натурального 
\begin_inset Formula $k$
\end_inset

 имеет место 
\begin_inset Formula $a^{k}\neq e$
\end_inset

.
\end_layout

\begin_layout Solution
Итак, все степени 
\begin_inset Formula $a$
\end_inset

 различны, но все степени 
\begin_inset Formula $a$
\end_inset

 принадлежат 
\begin_inset Formula $G$
\end_inset

, которые содержит конечное число элементов.
 Полученное противоречие означает, что 
\begin_inset Formula $a$
\end_inset

 — элемент конечного порядка, либо 
\begin_inset Formula $G$
\end_inset

 — группа бесконечного порядка.
\end_layout

\begin_layout Problem
Докажите, что если 
\begin_inset Formula $a$
\end_inset

 — элемент порядка 
\begin_inset Formula $n$
\end_inset

, то 
\begin_inset Formula $a^{-1}=a^{n-1}$
\end_inset

.
\end_layout

\begin_layout Solution
По определению степени 
\begin_inset Formula $aa^{n-1}=a^{n-1}a=a^{n}$
\end_inset

, а так как 
\begin_inset Formula $a$
\end_inset

 — элемент порядка 
\begin_inset Formula $n$
\end_inset

, то 
\begin_inset Formula $a^{n}=e$
\end_inset

.
 Таким образом, 
\begin_inset Formula $a^{n-1}$
\end_inset

 удовлетворяет определению обратного элемента для 
\begin_inset Formula $a$
\end_inset

.
 А так как обратный элемент единственный 
\begin_inset Note Note
status open

\begin_layout Plain Layout
добавить ссылку
\end_layout

\end_inset

, то 
\begin_inset Formula $a^{n-1}=a^{-1}$
\end_inset

.
\end_layout

\begin_layout Section
Подгруппы и циклические группы
\end_layout

\begin_layout Definition
Подмножество 
\begin_inset Formula $H$
\end_inset

 группы 
\begin_inset Formula $G$
\end_inset

 называется 
\emph on
подгруппой
\emph default
 
\begin_inset Formula $G$
\end_inset

, если 
\begin_inset Formula 
\[
e\in H,
\]

\end_inset


\begin_inset Formula 
\[
a\in H\Rightarrow a^{-1}\in H,
\]

\end_inset


\begin_inset Formula 
\[
a,b\in H\Rightarrow a\circ b\in H.
\]

\end_inset


\end_layout

\begin_layout Standard
Иными словами.
 чтобы быть подгруппой, 
\begin_inset Formula $H$
\end_inset

 должна быть одновременно подмножеством и группой.
 Из ассоциативности операции в 
\begin_inset Formula $G$
\end_inset

 следует её ассоциативность в 
\begin_inset Formula $H$
\end_inset

, поэтому в этом определении не нужно явно постулировать ассоциативность.
 По тем же причинам не нужно явно повторять аксиомы нейтральности и сокращения.
\end_layout

\begin_layout Standard
Например, аддитивная группа чётных чисел является подгруппой аддитивной
 группы целых чисел, равно как и аддитивная группа чисел, кратных 
\begin_inset Formula $5$
\end_inset

.
\end_layout

\begin_layout Standard
У некоторых групп много подгрупп, но почти у всех есть по меньшей мере две:
 сама подгрупп и группа, состоящая из одного элемента 
\begin_inset Formula $e$
\end_inset

.
 Эти две подгруппы называются 
\emph on
тривиальными 
\emph default
(единственная группа, у которой нет даже двух подгрупп, — группа, состоящая
 только из нейтрального элемента)
\emph on
.
\end_layout

\begin_layout Standard
\begin_inset Note Note
status open

\begin_layout Plain Layout
Пример про подгруппы группы ненулевых остатков от деления на 
\begin_inset Formula $7$
\end_inset


\end_layout

\end_inset


\end_layout

\begin_layout Problem
Найти порядок каждого элемента:
\end_layout

\begin_layout Problem
1) мультипликативной группы остатков по модулю 7.
\end_layout

\begin_layout Problem
2) мультипликативной группы остатков по модулю 11.
\end_layout

\begin_layout Solution
\begin_inset Note Note
status open

\begin_layout Plain Layout
Написать систему компьютерной алгебры, решающую эту задачу
\end_layout

\end_inset


\end_layout

\begin_layout Definition
Конечная группа называется 
\emph on
циклической
\emph default
, если в ней имеется такой элемент 
\begin_inset Formula $a$
\end_inset

, что для любого элемента 
\begin_inset Formula $b$
\end_inset

 найдётся целое число 
\begin_inset Formula $n$
\end_inset

, такое, что 
\begin_inset Formula 
\[
b=a^{n}.
\]

\end_inset


\end_layout

\begin_layout Definition
Такой элемент 
\begin_inset Formula $a$
\end_inset

 называется 
\emph on
образующим
\emph default
 или 
\emph on
порождающими
\emph default
.
\end_layout

\begin_layout Standard
В группе может быть несколько порождающих элементов.
 Например, в мультипликативной группе ненулевых остатков по модулю 7 образующими
 являются элементы 
\begin_inset Formula $3$
\end_inset

 и 
\begin_inset Formula $5$
\end_inset

, потому что они не входят ни в какую нетривиальную подгруппу исходной группы.
\end_layout

\begin_layout Problem
Докажите, что любая подгруппа циклической группы циклическая.
\end_layout

\begin_layout Solution
\begin_inset Note Note
status open

\begin_layout Plain Layout
Написать решение
\end_layout

\end_inset

Рассмотрим циклическую группу 
\begin_inset Formula $G$
\end_inset

 и некоторую её подгруппу 
\begin_inset Formula $H$
\end_inset

.
 Так как 
\begin_inset Formula $G$
\end_inset

 конечная по определению, то конечной является и 
\begin_inset Formula $H$
\end_inset

.
 Пусть 
\begin_inset Formula $H=\left\{ b_{1},\dots,b_{m}\right\} $
\end_inset

, где 
\begin_inset Formula $m$
\end_inset

 — порядок 
\begin_inset Formula $H$
\end_inset

.
 Так как 
\begin_inset Formula $G$
\end_inset

 циклическая, то элементы 
\begin_inset Formula $H$
\end_inset

 являются степенями некоторого 
\begin_inset Formula $a\in G$
\end_inset

.
 Пусть 
\begin_inset Formula $b_{i}=a^{n_{i}}$
\end_inset

 при 
\begin_inset Formula $i=1,\dots,m$
\end_inset

.
 Так как 
\begin_inset Formula $H$
\end_inset

 — подгруппа, то она включает в себя любой элемент вида 
\begin_inset Formula 
\[
\prod_{j=1}^{m}b_{j}^{k_{j}}=a^{\sum_{j=1}^{m}k_{j}n_{j}},
\]

\end_inset

 где 
\begin_inset Formula $k_{j}$
\end_inset

 — произвольные целые числа.
 В частности, можно взять такие 
\begin_inset Formula $k_{j}$
\end_inset

, что 
\begin_inset Note Note
status open

\begin_layout Plain Layout
Добавить ссылку
\end_layout

\end_inset

 
\begin_inset Formula 
\[
\sum_{j=1}^{m}k_{j}n_{j}=\gcd\left(n_{1},\dots,n_{m}\right)=d,
\]

\end_inset

поэтому 
\begin_inset Formula $b_{0}=a^{d}\in H$
\end_inset

.
 Тогда, по определению наибольшего общего делителя: 
\begin_inset Formula 
\[
n_{j}=d\cdot\left(\frac{n_{j}}{d}\right)=d\cdot s_{j},
\]

\end_inset

 где 
\begin_inset Formula 
\[
s_{j}=\frac{n_{j}}{d}.
\]

\end_inset


\end_layout

\begin_layout Solution
Поэтому
\end_layout

\begin_layout Solution
\begin_inset Formula 
\[
b_{j}=a^{n_{j}}=a^{d\cdot s_{j}}=b_{0}^{s_{j}}.
\]

\end_inset


\end_layout

\begin_layout Solution
Таким образом, 
\begin_inset Formula $b_{0}$
\end_inset

 является образующим 
\begin_inset Formula $H$
\end_inset

, а сама 
\begin_inset Formula $H$
\end_inset

 — циклическая.
\end_layout

\begin_layout Problem
Докажите, что любая циклическая группа абелева.
\end_layout

\begin_layout Solution
\begin_inset Note Note
status open

\begin_layout Plain Layout
Написать решение
\end_layout

\end_inset

В циклической группе все элементы являются степенями некоторого элемента,
 а степени одного элемента коммутируют 
\begin_inset Note Note
status open

\begin_layout Plain Layout
добавить ссылку
\end_layout

\end_inset

.
\end_layout

\begin_layout Lemma
Степени любого элемента 
\begin_inset Formula $a$
\end_inset

 конечной группы 
\begin_inset Formula $G$
\end_inset

 образуют подгруппу.
\end_layout

\begin_layout Proof
\begin_inset Note Note
status open

\begin_layout Plain Layout
Написать доказательство
\end_layout

\end_inset

Обозначим множество степеней 
\begin_inset Formula $a$
\end_inset

 как 
\begin_inset Formula $H$
\end_inset

.
 Проверим выполнение всех требований подгруппы.
 Прежде всего, степени любого элемента сами являются элементами этой группы,
 поэтому они образуют подмножество.
\end_layout

\begin_layout Proof
Так как, по определению, 
\begin_inset Formula $a^{0}=e$
\end_inset

, то 
\begin_inset Formula $e\in H$
\end_inset

.
\end_layout

\begin_layout Proof
Так как группа 
\begin_inset Formula $G$
\end_inset

 конечная, то конечной является и 
\begin_inset Formula $H$
\end_inset

.
 Тогда порядок элемента 
\begin_inset Formula $a$
\end_inset

 также конечен
\begin_inset Note Note
status open

\begin_layout Plain Layout
добавить ссылку
\end_layout

\end_inset

.
 Обозначим его как 
\begin_inset Formula $m$
\end_inset

.
 Рассмотрим произвольный элемент 
\begin_inset Formula $H$
\end_inset

.
 Он имеет вид 
\begin_inset Formula $a^{k}$
\end_inset

, где 
\begin_inset Formula $k$
\end_inset

 — натуральное число.
 Рассмотрим элемент 
\begin_inset Formula $a^{m-k}$
\end_inset

.
 По свойству степеней 
\begin_inset Note Note
status open

\begin_layout Plain Layout
добавить ссылку
\end_layout

\end_inset

, 
\begin_inset Formula 
\[
a^{k}\circ a^{m-k}=a^{m-k}\circ a^{k}=a^{m}=e.
\]

\end_inset


\end_layout

\begin_layout Proof
Так как 
\begin_inset Formula $0\le k\le m$
\end_inset

, то 
\begin_inset Formula $0\le m-k\le m$
\end_inset

, то есть 
\begin_inset Formula $a^{m-k}\in H$
\end_inset

, поскольку 
\begin_inset Formula $H$
\end_inset

 — группа степеней 
\begin_inset Formula $a$
\end_inset

.
\end_layout

\begin_layout Proof
Наконец, Рассмотрим два элемента группы 
\begin_inset Formula $H$
\end_inset

: 
\begin_inset Formula $a^{j}$
\end_inset

 и 
\begin_inset Formula $a^{k}$
\end_inset

, тогда 
\begin_inset Note Note
status open

\begin_layout Plain Layout
Добавить ссылку
\end_layout

\end_inset

 
\begin_inset Formula $a^{j}\circ a^{k}=a^{j+k}\in H$
\end_inset

, так как 
\begin_inset Formula $H$
\end_inset

 — группа степеней 
\begin_inset Formula $a$
\end_inset

.
\end_layout

\begin_layout Section
Теорема Лагранжа
\end_layout

\begin_layout Standard
Общая алгебра замечательна тем, что мы можем доказывать результаты о таких
 структурах, как группы, ничего не зная ни о конкретных элементах группы,
 ни о её операции.
\end_layout

\begin_layout Definition
Если 
\begin_inset Formula $G$
\end_inset

 — группа, а 
\begin_inset Formula $H\subset G$
\end_inset

 — подгруппа 
\begin_inset Formula $G$
\end_inset

, то для любого 
\begin_inset Formula $a\in G$
\end_inset

 левым смежным классом 
\begin_inset Formula $a$
\end_inset

 по 
\begin_inset Formula $H$
\end_inset

 называется множество 
\begin_inset Formula 
\[
aH=\left\{ g\in G|\exists h\in H:g=ah\right\} .
\]

\end_inset


\end_layout

\begin_layout Standard
Иначе говоря, левый смежный класс 
\begin_inset Formula $aH$
\end_inset

 — это множество всех элементов 
\begin_inset Formula $G$
\end_inset

, которые можно получить умножением элементов 
\begin_inset Formula $H$
\end_inset

 на 
\begin_inset Formula $a$
\end_inset

 слева.
\end_layout

\begin_layout Lemma
(размер смежных классов).
 В конечной группе 
\begin_inset Formula $G$
\end_inset

 для любой её подгруппы 
\begin_inset Formula $H$
\end_inset

 количество элементов в смежном классе 
\begin_inset Formula $aH$
\end_inset

 равно количеству элементов в самой подгруппе 
\begin_inset Formula $H$
\end_inset

.
\end_layout

\begin_layout Proof
Так как подгруппа является подмножеством, то по теореме
\begin_inset Note Note
status open

\begin_layout Plain Layout
Добавить ссылку на теорему 6.2
\end_layout

\end_inset

, между 
\begin_inset Formula $H$
\end_inset

 и 
\begin_inset Formula $aH$
\end_inset

 существует взаимно однозначное соответствие, следовательно в них одинаковое
 число элементов.
\end_layout

\begin_layout Lemma
(Полное покрытие смежными классами).
 Каждый элемент 
\begin_inset Formula $a$
\end_inset

 группы 
\begin_inset Formula $G$
\end_inset

 принадлежит какому-нибудь смежному классу подгруппы 
\begin_inset Formula $H$
\end_inset

.
\end_layout

\begin_layout Proof
Так как 
\begin_inset Formula $H$
\end_inset

 — подгруппа, то нейтральный элемент 
\begin_inset Formula $e$
\end_inset

 группы 
\begin_inset Formula $G$
\end_inset

 также принадлежит 
\begin_inset Formula $H$
\end_inset

.
 Таким образом, 
\begin_inset Formula $a\in aH$
\end_inset

, так как 
\begin_inset Formula $e\in H$
\end_inset

 и 
\begin_inset Formula $a=ae$
\end_inset

.
\end_layout

\begin_layout Lemma
(смежные класса не пересекаются или совпадают).
 Если у двух смежных классов 
\begin_inset Formula $aH$
\end_inset

 и 
\begin_inset Formula $bH$
\end_inset

 в группе 
\begin_inset Formula $G$
\end_inset

 имеется хотя бы один общий элемент 
\begin_inset Formula $c$
\end_inset

, то 
\begin_inset Formula $aH=bH$
\end_inset

.
\end_layout

\begin_layout Proof
Пусть 
\begin_inset Formula $c\in aH$
\end_inset

, докажем, что 
\begin_inset Formula $aH=cH$
\end_inset

.
 Так как 
\begin_inset Formula $c\in aH$
\end_inset

, то существует такой 
\begin_inset Formula $h_{c}\in H$
\end_inset

, что 
\begin_inset Formula $c=ah_{c}$
\end_inset

.
 Умножив это равенство на 
\begin_inset Formula $h_{c}^{-1}$
\end_inset

 справа, получим 
\begin_inset Formula $a=ch_{c}^{-1}$
\end_inset

.
 Так как 
\begin_inset Formula $H$
\end_inset

 — подгруппа и 
\begin_inset Formula $h_{c}\in H$
\end_inset

, то 
\begin_inset Formula $h_{c}^{-1}\in H$
\end_inset

 и, следовательно, 
\begin_inset Formula $a\in cH$
\end_inset

.
 
\end_layout

\begin_layout Proof
Рассмотрим теперь произвольный элемент 
\begin_inset Formula $x\in aH$
\end_inset

.
 По определению смежного класса, существует элемент 
\begin_inset Formula $h_{x}\in H$
\end_inset

, такой, что 
\begin_inset Formula $x=ah_{x}$
\end_inset

.
 Подставив в это равенство выражение 
\begin_inset Formula $a=ch_{c}^{-1}$
\end_inset

, получим 
\begin_inset Formula 
\[
x=ah_{x}=ch_{c}^{-1}h_{x}.
\]

\end_inset


\end_layout

\begin_layout Proof
Так как 
\begin_inset Formula $H$
\end_inset

 — подгруппа и 
\begin_inset Formula $h_{c},h_{x}\in H$
\end_inset

, то 
\begin_inset Formula $h_{c}^{-1}\in H$
\end_inset

 и 
\begin_inset Formula $h_{c}^{-1}h_{x}\in H$
\end_inset

.
 Поэтому 
\begin_inset Formula $x=c\left(h_{c}^{-1}h_{x}\right)\in cH$
\end_inset

.
 Мы показали, что из 
\begin_inset Formula $c\in aH$
\end_inset

 следует 
\begin_inset Formula $a\in cH$
\end_inset

 и 
\begin_inset Formula $aH\subset cH$
\end_inset

.
 Тогда из 
\begin_inset Formula $a\in cH$
\end_inset

 следует 
\begin_inset Formula $cH\subset aH$
\end_inset

.
 Окончательно получаем, что из 
\begin_inset Formula $c\in aH$
\end_inset

 следует 
\begin_inset Formula $aH=cH$
\end_inset

.
\end_layout

\begin_layout Proof
Так как, по условию, 
\begin_inset Formula $c\in bH$
\end_inset

, то, по доказанному выше, 
\begin_inset Formula $bH=cH$
\end_inset

.
 Таким образом, 
\begin_inset Formula $aH=cH=bH$
\end_inset

, что и требовалось доказать\SpecialChar endofsentence

\end_layout

\begin_layout Standard
Располагая этими результатами, мы можем доказать важную теорему из теории
 групп, которая иллюстрирует мощь абстрактных рассуждений.
\end_layout

\begin_layout Theorem
(Теореме Лагранжа).
 Порядок любой подгруппы 
\begin_inset Formula $H$
\end_inset

 конечной группы 
\begin_inset Formula $G$
\end_inset

 делит порядок группы.
\end_layout

\begin_layout Proof
Рассмотрим всевозможные левые смежные классы группы 
\begin_inset Formula $G$
\end_inset

 по подгруппе 
\begin_inset Formula $H$
\end_inset

.
 Этих классов не более, чем элементов в группе 
\begin_inset Formula $G$
\end_inset

, то есть некоторое конечное число 
\begin_inset Formula $n$
\end_inset

.
 Так как 
\begin_inset Formula $H$
\end_inset

 — подгруппа, а значит и подмножество, 
\begin_inset Formula $G$
\end_inset

, то её порядок также является некоторым конечным числом 
\begin_inset Formula $m$
\end_inset

.
 Количество левых смежных классов может быть меньше 
\begin_inset Formula $n$
\end_inset

, так как разные элементы могут порождать один и тот же левый смежный класс.
 Пусть количество левых смежных классов равно 
\begin_inset Formula $d$
\end_inset

.
 Смежные классы не пересекаются 
\begin_inset Note Note
status open

\begin_layout Plain Layout
добавить ссылку на лемму 6.4
\end_layout

\end_inset

 и покрывают всю группу 
\begin_inset Formula $G$
\end_inset

 
\begin_inset Note Note
status open

\begin_layout Plain Layout
Добавить ссылку на лемму 6.5
\end_layout

\end_inset

, поэтому сумма количества элементов в каждом классе равна, с одной стороны
 
\begin_inset Formula $m\cdot d$
\end_inset

, а с другой — 
\begin_inset Formula $n$
\end_inset

, таким образом: 
\begin_inset Formula $n=md$
\end_inset

, то есть 
\begin_inset Formula $n$
\end_inset

 делится нацело на 
\begin_inset Formula $m$
\end_inset

.
\end_layout

\begin_layout Standard
Интересно, что обращение теоремы Лагранжа не верно: если порядок группы
 делится на некоторое число 
\begin_inset Formula $m$
\end_inset

, то у группы может и не быть подгруппы порядка 
\begin_inset Formula $m$
\end_inset

.
\end_layout

\begin_layout Proposition
Порядок любого элемента конечной группы делит порядок группы.
\end_layout

\begin_layout Proof
Рассмотрим произвольную группу 
\begin_inset Formula $G$
\end_inset

 и произвольный элемент этой группы 
\begin_inset Formula $a$
\end_inset

.
 По лемме 6.2 
\begin_inset Note Note
status open

\begin_layout Plain Layout
Добавить ссылку
\end_layout

\end_inset

, степени 
\begin_inset Formula $a$
\end_inset

 образуют подгруппу группы 
\begin_inset Formula $G$
\end_inset

.
 Порядок этой группы равен порядку элемента 
\begin_inset Formula $a$
\end_inset


\begin_inset Note Note
status open

\begin_layout Plain Layout
доказать или сослаться
\end_layout

\end_inset

.
 По теореме Лагранжа 
\begin_inset Note Note
status open

\begin_layout Plain Layout
Добавить ссылку
\end_layout

\end_inset

, порядок этой подгруппы делит порядок группы 
\begin_inset Formula $G$
\end_inset

, а значит и порядок элемента делит порядок группы.
\end_layout

\begin_layout Proposition
Если группа 
\begin_inset Formula $G$
\end_inset

 имеет порядок 
\begin_inset Formula $n$
\end_inset

 и 
\begin_inset Formula $a\in G$
\end_inset

, то 
\begin_inset Formula $a^{n}=e$
\end_inset

.
\end_layout

\begin_layout Proof
По доказанному выше
\begin_inset Note Note
status open

\begin_layout Plain Layout
Добавить ссылку
\end_layout

\end_inset

, порядок 
\begin_inset Formula $a$
\end_inset

 (обозначим его как 
\begin_inset Formula $m$
\end_inset

) делит 
\begin_inset Formula $n$
\end_inset

, то есть существует такое целое 
\begin_inset Formula $d$
\end_inset

, что 
\begin_inset Formula $n=md$
\end_inset

.
 По определению порядка элемента, 
\begin_inset Formula $a^{m}=e$
\end_inset

, поэтому 
\begin_inset Formula 
\[
a^{n}=\left(a^{m}\right)^{d}=e^{d}=e,
\]

\end_inset

 что и требовалось.
\end_layout

\begin_layout Standard
Теорема Лагранжа позволяет доказать некоторые важные результаты из главы
 5
\begin_inset Note Note
status open

\begin_layout Plain Layout
Добавить ссылку
\end_layout

\end_inset

 проще, чем это было сделано раньше.
\end_layout

\begin_layout Theorem*
(Малая теорема Ферма).
 Если 
\begin_inset Formula $p$
\end_inset

 простое, то 
\begin_inset Formula $a^{p-1}-1$
\end_inset

 делится на 
\begin_inset Formula $p$
\end_inset

 для любого 
\begin_inset Formula $0<a<p$
\end_inset

.
\end_layout

\begin_layout Proof
\begin_inset Note Note
status open

\begin_layout Plain Layout
Написать теоретико-групповое доказательство
\end_layout

\end_inset

Возьмём в качестве 
\begin_inset Formula $G$
\end_inset

 мультипликативную группу остатков от деления на 
\begin_inset Formula $p$
\end_inset

.
 Порядок этой группы равен 
\begin_inset Formula $p-1$
\end_inset

, 
\begin_inset Formula $a\in G$
\end_inset

 по условию, поэтому, как было показано выше 
\begin_inset Note Note
status open

\begin_layout Plain Layout
добавить ссылку
\end_layout

\end_inset

, 
\begin_inset Formula $a^{p-1}=1\mod p$
\end_inset

 или 
\begin_inset Formula $a^{p-1}-1=0\mod p$
\end_inset

.
\end_layout

\begin_layout Theorem*
(Теорема Эйлера).Если 
\begin_inset Formula $a$
\end_inset

 и 
\begin_inset Formula $n$
\end_inset

 взаимно просты, то 
\begin_inset Formula $a^{\phi\left(n\right)}-1$
\end_inset

 делится на 
\begin_inset Formula $n$
\end_inset

.
\end_layout

\begin_layout Proof
Рассмотрим мультипликативную группу обратимых остатков от деления на 
\begin_inset Formula $n$
\end_inset

.
 Она содержит 
\begin_inset Formula $\phi\left(n\right)$
\end_inset

 элементов, поэтому для 
\begin_inset Formula $a$
\end_inset

, таких, что 
\begin_inset Formula $1\le a\le n$
\end_inset

 и 
\begin_inset Formula $a$
\end_inset

 взаимно просто с 
\begin_inset Formula $n$
\end_inset

, имеет место 
\begin_inset Formula $a^{\phi\left(n\right)}=1\mod n$
\end_inset

 или 
\begin_inset Formula $a^{\phi\left(n\right)}-1\mod n$
\end_inset

.
 Пусть теперь 
\begin_inset Formula $a>n$
\end_inset

, но 
\begin_inset Formula $a$
\end_inset

 и 
\begin_inset Formula $n$
\end_inset

 взаимно просты.
 Тогда 
\begin_inset Formula $a=qn+r$
\end_inset

, где 
\begin_inset Formula $0<r<n$
\end_inset

 (
\begin_inset Formula $r\neq0$
\end_inset

, так как в противном случае 
\begin_inset Formula $a=qn$
\end_inset

, то есть 
\begin_inset Formula $a$
\end_inset

 и 
\begin_inset Formula $n$
\end_inset

 не взаимно просты).
 Тогда 
\begin_inset Formula $a^{\phi\left(n\right)}\mod n=r^{\phi\left(n\right)}\mod n$
\end_inset


\begin_inset Note Note
status open

\begin_layout Plain Layout
Наверное, нужно доказать выше, что 
\begin_inset Formula $b^{m}\mod n=\left(b\mod n\right)^{m}\mod n$
\end_inset


\end_layout

\end_inset

.
\end_layout

\begin_layout Problem
(Очень лёгкое).
 Какие подгруппы имеет группа порядка 101?
\end_layout

\begin_layout Solution
Так как 101 — простое число, то у группы порядка 101 есть только две подгруппы:
 сама эта группа (порядка 101) и группа, состоящая только из нейтрального
 элемента (порядка 1).
\end_layout

\begin_layout Problem
Докажите, что любая группа простого порядка циклическая.
\end_layout

\begin_layout Solution
Как было показано выше
\begin_inset Note Note
status open

\begin_layout Plain Layout
Добавить ссылку
\end_layout

\end_inset

, порядок элемента группы является делителем порядка группы.
 Так как делителями простого числа являются только единица и само это число,
 то в группе простого порядка 
\begin_inset Formula $p$
\end_inset

 все элементы имеют порядок 1 или 
\begin_inset Formula $p$
\end_inset

.
 Единственный элемент порядка 1 — это нейтральный элемент 
\begin_inset Note Note
status open

\begin_layout Plain Layout
Добавить ссылку
\end_layout

\end_inset

.
 Так как 
\begin_inset Formula $p>1$
\end_inset

, то в группе существуют другие элементы, возьмём любой из них и обозначим
 как 
\begin_inset Formula $a$
\end_inset

.
 Порядок этого элемента, равен 
\begin_inset Formula $p$
\end_inset

.
 Элементы 
\begin_inset Formula $a^{k}$
\end_inset

 при 
\begin_inset Formula $k=0,1,\dots,p-1$
\end_inset

 различны
\begin_inset Note Note
status open

\begin_layout Plain Layout
доказать или добавить ссылку
\end_layout

\end_inset

 и являются элементами рассматриваемой группы.
 Таким образом, все 
\begin_inset Formula $p$
\end_inset

 элементов группы являются степенями любого её элемента (кроме нейтрального).
 
\end_layout

\begin_layout Section
Теории и модели
\end_layout

\begin_layout Standard
Группы, моноиды и полугруппы — примеры того, что математики теориями.
\end_layout

\begin_layout Definition
Теорией называется множество истинных предложений.
\end_layout

\begin_layout Itemize
теория может быть порождена набором аксиом, дополненными правилами вывода;
\end_layout

\begin_layout Itemize
теория называется 
\emph on
конечно аксиоматизируемой
\emph default
, если может быть порождена конечным набором аксиом;
\end_layout

\begin_layout Itemize
набор аксиом называется 
\emph on
независимым
\emph default
, если удаление из него любой аксиомы приводит к уменьшению множества истинных
 предложений;
\end_layout

\begin_layout Itemize
теория называется 
\emph on
полной
\emph default
, если для любого предложения она содержит либо само это предложение, либо
 его отрицание;
\end_layout

\begin_layout Itemize
теория называется 
\emph on
непротиворечивой
\emph default
, если не существует предложения, для которого теория содержит как его само,
 так и его отрицание.
\end_layout

\begin_layout Standard
Мы не собираемся перечислять все предложения, составляющие теорию групп.
 Вместо этого мы порождаем предложения, выводя их из аксиом и ранее доказанных
 предложений.
\end_layout

\begin_layout Definition
Множество элементов, для которого определены все операции теории и истины
 все предложения теории, называется 
\emph on
моделью 
\emph default
теории.
\end_layout

\begin_layout Standard
В некотором смысле, чем больше предложений в теории, тем меньше её различных
 моделей.
 Это имеет интуитивный смысл: аксиомы и предложения можно рассматривать
 как 
\emph on
ограничения 
\emph default
теории; чем их больше, тем труднее им всем удовлетворить, и, стало быть,
 тем меньше моделей способны это сделать.
\end_layout

\begin_layout Definition
Две модели называются 
\emph on
изоморфными
\emph default
, если между ними можно установить взаимно однозначное соответствие, сохраняющее
 операции.
 Это означает, что отображение (или обратное к нему) можно применить как
 до, так и после операции — результат получится одинаковый.
\end_layout

\begin_layout Standard
\begin_inset Separator plain
\end_inset


\end_layout

\begin_layout Definition
Непротиворечивая теория называется 
\emph on
категоричной
\emph default
, или 
\emph on
унивалентной
\emph default
, если все её модели изоморфны.
 Это оригинальное определение Освальда Веблена.
 В современной логике применяется понятие 
\begin_inset Formula $k$
\end_inset

-категоричной теории, для которой все модели мощности 
\begin_inset Formula $k$
\end_inset

 изоморфны.
\end_layout

\begin_layout Standard
У противоречивой теории вообще нет моделей — невозможно удовлетворить всем
 предложениям, не придя к противоречию.
\end_layout

\begin_layout Section
Примеры категоричных и не категоричных теорий
\end_layout

\begin_layout Standard
Пример категоричной теории — циклическая группа порядка 
\begin_inset Formula $4$
\end_inset

.
\end_layout

\begin_layout Standard
Пример не категоричной теории — произвольная группа 
\begin_inset Formula $4$
\end_inset

.
 Существует две неизоморфные группы: циклическая группа порядка 
\begin_inset Formula $4$
\end_inset

 и группа Клейна (группа симметрий прямоугольника).
\end_layout

\begin_layout Standard
\begin_inset Tabular
<lyxtabular version="3" rows="6" columns="5">
<features tabularvalignment="middle">
<column alignment="center" valignment="top">
<column alignment="center" valignment="top">
<column alignment="center" valignment="top">
<column alignment="center" valignment="top">
<column alignment="center" valignment="top">
<row>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Структура
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Операции
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Элементы
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Аксиомы
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Пример
\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Магма
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $x\circ y$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Полугруппа
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $x\circ y$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $x\circ\left(y\circ z\right)=\left(x\circ y\right)\circ z$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $\left(\mathbb{Z^{+}},+\right)$
\end_inset


\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Моноид
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $x\circ y$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $e$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $\begin{array}{c}
x\circ\left(y\circ z\right)=\left(x\circ y\right)\circ z\\
x\circ e=e\circ x=x
\end{array}$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Строки с операцией конкатенации
\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Группа
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $x\circ y,x^{-1}$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $e$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $\begin{array}{c}
x\circ\left(y\circ z\right)=\left(x\circ y\right)\circ z\\
x\circ e=e\circ x=x\\
x\circ x^{-1}=x^{-1}\circ x=e
\end{array}$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Обратимые матрицы с операцией умножения
\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Абелева группа
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $x\circ y,x^{-1}$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $e$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $\begin{array}{c}
x\circ\left(y\circ z\right)=\left(x\circ y\right)\circ z\\
x\circ e=e\circ x=x\\
x\circ x^{-1}=x^{-1}\circ x=e\\
x\circ y=y\circ x
\end{array}$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Двумерные векторы с операцией сложения
\end_layout

\end_inset
</cell>
</row>
</lyxtabular>

\end_inset


\end_layout

\begin_layout Chapter
Вывод обобщённого алгоритма
\end_layout

\begin_layout Standard
\begin_inset Note Note
status open

\begin_layout Plain Layout
Эта глава больше относится к программированию, кроме, пожалуй, раздела 7.7
\end_layout

\end_inset


\end_layout

\begin_layout Section
Вычисление чисел Фибоначчи
\end_layout

\begin_layout Standard
Последовательность чисел Фибоначчи формально определяется следующим образом:
 
\begin_inset Formula 
\[
F_{n}=\begin{cases}
0, & n=0,\\
1, & n=1,\\
F_{n-1}+F_{n-2}, & n\ge2.
\end{cases}
\]

\end_inset


\end_layout

\begin_layout Standard
Наивная реализация на C++ могла бы выглядеть так:
\end_layout

\begin_layout Standard
\begin_inset listings
inline false
status open

\begin_layout Plain Layout

int fin0(int n)
\end_layout

\begin_layout Plain Layout

{
\end_layout

\begin_layout Plain Layout

	if(n == 0) return 0;
\end_layout

\begin_layout Plain Layout

	if(n == 1) return 1;
\end_layout

\begin_layout Plain Layout

	return fib0(n-1) + fib0(n-2);
\end_layout

\begin_layout Plain Layout

}
\end_layout

\end_inset


\end_layout

\begin_layout Standard
Однако этот код снова и снова выполняется одни и те же действия.
\end_layout

\begin_layout Exercise
Сколько сложений необходимо для вычисления fib0(n)?
\end_layout

\begin_layout Solution
Обозначим искомое количество как 
\begin_inset Formula $A_{n}$
\end_inset

.
 Очевидно, 
\begin_inset Formula $A_{0}=A_{1}=0$
\end_inset

.
 При 
\begin_inset Formula $n\ge2$
\end_inset

 требуется 
\begin_inset Formula $A_{n-1}+A_{n-2}+1$
\end_inset

 сложений (сначала вычисляем слагаемые, а затем — выполняем одно сложение
 для получения окончательного результата) Найдём несколько следующих значений.
 
\begin_inset Formula 
\[
A_{2}=A_{1}+A_{0}+1=1,
\]

\end_inset


\begin_inset Formula 
\[
A_{3}=A_{2}+A_{1}+1=1+1=2,
\]

\end_inset


\begin_inset Formula 
\[
A_{4}=A_{3}+A_{1}+1=2+1+1=4,
\]

\end_inset


\begin_inset Formula 
\[
A_{5}=A_{4}+A_{3}+1=4+2+1=7,
\]

\end_inset


\begin_inset Formula 
\[
A_{6}=A_{5}+A_{4}+1=7+4+1=12.
\]

\end_inset


\end_layout

\begin_layout Standard
Воспользуемся аппаратом производящих функций.
 Рассмотрим функцию 
\begin_inset Formula 
\[
A\left(z\right)=\sum_{n=0}^{\infty}A_{n}z^{n}.
\]

\end_inset


\end_layout

\begin_layout Standard
\begin_inset Formula 
\begin{multline*}
A\left(z\right)=A_{0}+A_{1}z+\sum_{n=2}^{\infty}A_{n}z^{n}=\\
=A_{0}+A_{1}z+\sum_{n=2}^{\infty}\left(A_{n-1}+A_{n-2}+1\right)z^{n}=\\
=A_{0}+A_{1}z+z\sum_{n=2}^{\infty}A_{n-1}z^{n-1}+z^{2}\sum_{n=2}^{\infty}A_{n-2}z^{n-2}+\sum_{n=0}^{\infty}z^{n}=\\
=A_{0}+A_{1}z+z\sum_{n=1}^{\infty}A_{n}z^{n}+z^{2}\sum_{n=0}^{\infty}A_{n}z^{n-2}+\sum_{n=0}^{\infty}z^{n}=\\
=A_{0}+A_{1}z+z\left(A\left(z\right)-A_{0}\right)+z^{2}A\left(z\right)+\frac{1}{1-z}=\\
=A\left(z\right)\left(z+z^{2}\right)+A_{0}+\left(A_{1}-A_{0}\right)z+\frac{1}{1-z}.
\end{multline*}

\end_inset


\end_layout

\begin_layout Standard
Так как 
\begin_inset Formula $A_{0}=A_{1}=0$
\end_inset

, то: 
\begin_inset Formula 
\[
A\left(z\right)=A\left(z\right)\left(z+z^{2}\right)+\frac{1}{1-z}.
\]

\end_inset


\end_layout

\begin_layout Standard
Выразим 
\begin_inset Formula $A\left(z\right)$
\end_inset

 из этого уравнения:
\end_layout

\begin_layout Standard
\begin_inset Formula 
\[
A\left(z\right)\left[1-z-z^{2}\right]=\frac{1}{1-z}.
\]

\end_inset


\end_layout

\begin_layout Standard
Решим уравнение 
\begin_inset Formula $z^{2}+z-1=0$
\end_inset

, чтобы разложить 
\begin_inset Formula $1-z-z^{2}$
\end_inset

 на множители.
 
\begin_inset Formula 
\[
D=1+4=5,
\]

\end_inset


\begin_inset Formula 
\[
z_{1,2}=\frac{-1\pm\sqrt{5}}{2},
\]

\end_inset


\end_layout

\begin_layout Standard
\begin_inset Note Note
status open

\begin_layout Plain Layout
Дописать решение
\end_layout

\end_inset


\end_layout

\begin_layout Exercise
Реализуйте вычисление чисел Фибоначчи с помощью алгоритма power.
\end_layout

\begin_layout Solution
\begin_inset Note Note
status open

\begin_layout Plain Layout
Написать решение
\end_layout

\end_inset


\end_layout

\begin_layout Definition
Линейной рекуррентной функцией порядка 
\begin_inset Formula $k$
\end_inset

 называется функция 
\begin_inset Formula 
\[
f\left(y_{0},\dots,y_{k-1}\right)=\sum_{j=0}^{k-1}a_{j}y_{j}.
\]

\end_inset


\end_layout

\begin_layout Standard
\begin_inset Separator plain
\end_inset


\end_layout

\begin_layout Definition
Линейной рекуррентной последовательностью называется последовательность,
 порождаемая линейной рекуррентной функцией по 
\begin_inset Formula $k$
\end_inset

 начальным значениям.
\end_layout

\begin_layout Standard
Наивная реализация на C++ могла бы выглядеть так:
\end_layout

\begin_layout Standard
\begin_inset listings
inline false
status open

\begin_layout Plain Layout

int fin0(int n)
\end_layout

\begin_layout Plain Layout

{
\end_layout

\begin_layout Plain Layout

	if(n == 0) return 0;
\end_layout

\begin_layout Plain Layout

	if(n == 1) return 1;
\end_layout

\begin_layout Plain Layout

	return fib0(n-1) + fib0(n-2);
\end_layout

\begin_layout Plain Layout

}
\end_layout

\end_inset


\end_layout

\begin_layout Standard
Однако этот код снова и снова выполняется одни и те же действия.
\end_layout

\begin_layout Exercise
Сколько сложений необходимо для вычисления fib0(n)?
\end_layout

\begin_layout Solution
Обозначим искомое количество как 
\begin_inset Formula $A_{n}$
\end_inset

.
 Очевидно, 
\begin_inset Formula $A_{0}=A_{1}=0$
\end_inset

.
 При 
\begin_inset Formula $n\ge2$
\end_inset

 требуется 
\begin_inset Formula $A_{n-1}+A_{n-2}+1$
\end_inset

 сложений (сначала вычисляем слагаемые, а затем — выполняем одно сложение
 для получения окончательного результата) Найдём несколько следующих значений.
 
\begin_inset Formula 
\[
A_{2}=A_{1}+A_{0}+1=1,
\]

\end_inset


\begin_inset Formula 
\[
A_{3}=A_{2}+A_{1}+1=1+1=2,
\]

\end_inset


\begin_inset Formula 
\[
A_{4}=A_{3}+A_{1}+1=2+1+1=4,
\]

\end_inset


\begin_inset Formula 
\[
A_{5}=A_{4}+A_{3}+1=4+2+1=7,
\]

\end_inset


\begin_inset Formula 
\[
A_{6}=A_{5}+A_{4}+1=7+4+1=12.
\]

\end_inset


\end_layout

\begin_layout Standard
Воспользуемся аппаратом производящих функций.
 Рассмотрим функцию 
\begin_inset Formula 
\[
A\left(z\right)=\sum_{n=0}^{\infty}A_{n}z^{n}.
\]

\end_inset


\end_layout

\begin_layout Standard
\begin_inset Formula 
\begin{multline*}
A\left(z\right)=A_{0}+A_{1}z+\sum_{n=2}^{\infty}A_{n}z^{n}=\\
=A_{0}+A_{1}z+\sum_{n=2}^{\infty}\left(A_{n-1}+A_{n-2}+1\right)z^{n}=\\
=A_{0}+A_{1}z+z\sum_{n=2}^{\infty}A_{n-1}z^{n-1}+z^{2}\sum_{n=2}^{\infty}A_{n-2}z^{n-2}+\sum_{n=0}^{\infty}z^{n}=\\
=A_{0}+A_{1}z+z\sum_{n=1}^{\infty}A_{n}z^{n}+z^{2}\sum_{n=0}^{\infty}A_{n}z^{n-2}+\sum_{n=0}^{\infty}z^{n}=\\
=A_{0}+A_{1}z+z\left(A\left(z\right)-A_{0}\right)+z^{2}A\left(z\right)+\frac{1}{1-z}=\\
=A\left(z\right)\left(z+z^{2}\right)+A_{0}+\left(A_{1}-A_{0}\right)z+\frac{1}{1-z}.
\end{multline*}

\end_inset


\end_layout

\begin_layout Standard
Так как 
\begin_inset Formula $A_{0}=A_{1}=0$
\end_inset

, то: 
\begin_inset Formula 
\[
A\left(z\right)=A\left(z\right)\left(z+z^{2}\right)+\frac{1}{1-z}.
\]

\end_inset


\end_layout

\begin_layout Standard
Выразим 
\begin_inset Formula $A\left(z\right)$
\end_inset

 из этого уравнения:
\end_layout

\begin_layout Standard
\begin_inset Formula 
\[
A\left(z\right)\left[1-z-z^{2}\right]=\frac{1}{1-z}.
\]

\end_inset


\end_layout

\begin_layout Standard
Решим уравнение 
\begin_inset Formula $z^{2}+z-1=0$
\end_inset

, чтобы разложить 
\begin_inset Formula $1-z-z^{2}$
\end_inset

 на множители.
 
\begin_inset Formula 
\[
D=1+4=5,
\]

\end_inset


\begin_inset Formula 
\[
z_{1,2}=\frac{-1\pm\sqrt{5}}{2},
\]

\end_inset


\end_layout

\begin_layout Standard
\begin_inset Note Note
status open

\begin_layout Plain Layout
Дописать решение
\end_layout

\end_inset


\end_layout

\begin_layout Exercise
Реализуйте вычисление чисел Фибоначчи с помощью алгоритма power.
\end_layout

\begin_layout Solution
\begin_inset Note Note
status open

\begin_layout Plain Layout
Написать решение
\end_layout

\end_inset


\end_layout

\begin_layout Definition
Линейной рекуррентной функцией порядка 
\begin_inset Formula $k$
\end_inset

 называется функция 
\begin_inset Formula 
\[
f\left(y_{0},\dots,y_{k-1}\right)=\sum_{j=0}^{k-1}a_{j}y_{j}.
\]

\end_inset


\end_layout

\begin_layout Standard
\begin_inset Separator plain
\end_inset


\end_layout

\begin_layout Definition
Линейной рекуррентной последовательностью называется последовательность,
 порождаемая линейной рекуррентной функцией по 
\begin_inset Formula $k$
\end_inset

 начальным значениям.
\end_layout

\begin_layout Chapter
Ещё об алгебраических структурах
\end_layout

\begin_layout Section
Стевин, полиномы и НОД
\end_layout

\begin_layout Standard
Рассмотрим алгоритм вычисления значений многочлена:
\end_layout

\begin_layout Standard
\begin_inset listings
inline false
status open

\begin_layout Plain Layout

template <InputIterator I, Semigroup R>
\end_layout

\begin_layout Plain Layout

R polynomial_value(I first, I last, R x)
\end_layout

\begin_layout Plain Layout

{
\end_layout

\begin_layout Plain Layout

	if(first == last) return R(0);
\end_layout

\begin_layout Plain Layout

	R sum(*first);
\end_layout

\begin_layout Plain Layout

	while(++first != last)
\end_layout

\begin_layout Plain Layout

	{
\end_layout

\begin_layout Plain Layout

		sum *= x;
\end_layout

\begin_layout Plain Layout

		sum += *first;
\end_layout

\begin_layout Plain Layout

	}
\end_layout

\begin_layout Plain Layout

	return sum;
\end_layout

\begin_layout Plain Layout

}
\end_layout

\end_inset


\end_layout

\begin_layout Problem
Какие требования предъявляются к 
\series bold
R 
\series default
и типу значений итератора? Иными словами, каковы требования к коэффициентам
 полинома и их значениям?
\end_layout

\begin_layout Solution
\begin_inset Note Note
status open

\begin_layout Plain Layout
Написать решение
\end_layout

\end_inset


\end_layout

\begin_layout Standard
Революционный прорыв Стевина позволил рассматривать полиномы как числа и
 производить над ними обычные арифметические операции.
\end_layout

\begin_layout Standard
\begin_inset Note Note
status open

\begin_layout Plain Layout
Описать операции над многочленами
\end_layout

\end_inset


\end_layout

\begin_layout Definition
Степенью многочлена 
\begin_inset Formula $\deg\left(P\right)$
\end_inset

 называется самая старшая степень переменной с ненулевым коэффициентом.
\end_layout

\begin_layout Standard
\begin_inset Separator plain
\end_inset


\end_layout

\begin_layout Definition
Многочлен 
\begin_inset Formula $a$
\end_inset

 делиться на многочлен 
\begin_inset Formula $b$
\end_inset

 с остатком, если существует такие многочлены 
\begin_inset Formula $q$
\end_inset

 и 
\begin_inset Formula $r$
\end_inset

, что 
\begin_inset Formula 
\[
a=bq+r,\deg\left(r\right)<\deg\left(b\right).
\]

\end_inset


\end_layout

\begin_layout Problem
Докажите, что для любых двух многочленов 
\begin_inset Formula $p$
\end_inset

 и 
\begin_inset Formula $q$
\end_inset

:
\end_layout

\begin_layout Problem
1) 
\begin_inset Formula $p\left(x\right)=q\left(x\right)\cdot\left(x-x_{0}\right)+r\Rightarrow p\left(x_{0}\right)=r$
\end_inset

.
\end_layout

\begin_layout Problem
2) 
\begin_inset Formula $p\left(x_{0}\right)=0\Rightarrow p\left(x\right)=q\left(x\right)\cdot\left(x-x_{0}\right).$
\end_inset


\end_layout

\begin_layout Solution
1) Непосредственной подстановкой убеждаемся, что 
\begin_inset Formula 
\[
p\left(x_{0}\right)=q\left(x_{0}\right)\cdot\left(x_{0}-x_{0}\right)+r=q\left(x_{0}\right)\cdot0+r=0+r=r.
\]

\end_inset


\end_layout

\begin_layout Solution
2) Разделим 
\begin_inset Formula $p\left(x\right)$
\end_inset

 на 
\begin_inset Formula $\left(x-x_{0}\right)$
\end_inset

 с остатком.
 Так как степень остатка меньше степени делителя, а 
\begin_inset Formula $\left(x-x_{0}\right)$
\end_inset

 — многочлен первой степени, то остаток будет многочленом степени не выше
 1, то есть просто числом: 
\begin_inset Formula 
\[
p\left(x\right)=q\left(x\right)\cdot\left(x-x_{0}\right)+r.
\]

\end_inset

 Тогда, по доказанному в пункте 1), 
\begin_inset Formula $p\left(x_{0}\right)=r=0$
\end_inset

, то есть 
\begin_inset Formula 
\[
p\left(x\right)=q\left(x\right)\cdot\left(x-x_{0}\right).
\]

\end_inset


\end_layout

\begin_layout Standard
Стевин понял, что для вычисления НОД двух многочленов можно использовать
 все тот же алгоритм Евклида, нужно только изменить типы.
 Чтобы понять, что алгоритм завершается, нужно вспомнить, что степень остатка
 не выше степени делителя, поэтому степень многочлена на каждом шаге уменьшается
, а так как степень неотрицательное число, то убывающая последовательность
 степеней должна быть конечной.
\end_layout

\begin_layout Problem
Найдите НОД следующих многочленов:
\end_layout

\begin_layout Problem
1.
 
\begin_inset Formula $16x^{4}-56x^{3}-88x^{2}+278x+105$
\end_inset


\end_layout

\begin_layout Problem
\begin_inset Formula $16x^{4}-64x^{3}-44x^{2}+232x+70$
\end_inset


\end_layout

\begin_layout Problem
2.
 
\begin_inset Formula $7x^{4}+6x^{3}-8x^{2}-6x+1$
\end_inset


\end_layout

\begin_layout Problem
\begin_inset Formula $11x^{4}+15x^{3}-2x^{2}-5x+1.$
\end_inset


\end_layout

\begin_layout Problem
3.
 
\begin_inset Formula $nx^{n+1}-\left(n+1\right)x^{n}+1$
\end_inset

,
\end_layout

\begin_layout Problem
\begin_inset Formula $x^{n}-nx+\left(n-1\right)$
\end_inset


\end_layout

\begin_layout Solution
\begin_inset Note Note
status open

\begin_layout Plain Layout
написать систему компьютерной алгебры, которая могла бы решить эту задачу
\end_layout

\end_inset


\end_layout

\begin_layout Section
Геттинген и немецкая математика
\end_layout

\begin_layout Standard
\begin_inset Note Note
status open

\begin_layout Plain Layout
Определение комплексных чисел и Гауссовых чисел
\end_layout

\end_inset


\end_layout

\begin_layout Section
Нётер и рождение общей алгебры
\end_layout

\begin_layout Standard
\begin_inset Note Note
status open

\begin_layout Plain Layout
В основном — биографический раздел
\end_layout

\end_inset


\end_layout

\begin_layout Section
Кольца
\end_layout

\begin_layout Definition
Кольцом
\begin_inset Foot
status open

\begin_layout Plain Layout
Термин 
\begin_inset Quotes rld
\end_inset

кольцо
\begin_inset Quotes rrd
\end_inset

, предложенный Гильбертом, задумывался как метафора сообщества (круга) людей,
 объединённых общим предприятием, например шайка (англ.
 ring) преступников
\end_layout

\end_inset

 называется множество, на котором определены операции сложения, умножения
 и взятия обратного элемента по сложению, а также в котором существуют константы
 
\begin_inset Formula $0$
\end_inset

 и 
\begin_inset Formula $1$
\end_inset

, для которых выполняются следующие аксиомы:
\end_layout

\begin_layout Definition
\begin_inset Formula 
\[
x+\left(y+z\right)=\left(x+y\right)+z;
\]

\end_inset


\begin_inset Formula 
\[
x+0=0+x=x;
\]

\end_inset


\begin_inset Formula 
\[
x+\left(-x\right)=\left(-x\right)+x=0;
\]

\end_inset


\begin_inset Formula 
\[
x+y=y+x;
\]

\end_inset


\begin_inset Formula 
\[
x\left(yz\right)=\left(xy\right)z;
\]

\end_inset


\begin_inset Formula 
\[
1\neq0;
\]

\end_inset


\begin_inset Formula 
\[
1x=x1=x;
\]

\end_inset


\begin_inset Formula 
\[
0x=x0=0;
\]

\end_inset


\begin_inset Formula 
\[
x\left(y+z\right)=xy+xz;
\]

\end_inset


\begin_inset Formula 
\[
\left(y+z\right)x=yx+zx.
\]

\end_inset


\end_layout

\begin_layout Definition
\begin_inset Note Note
status open

\begin_layout Plain Layout
Нельзя ли вывести 
\begin_inset Formula $0x=x0=0$
\end_inset

?
\end_layout

\end_inset


\end_layout

\begin_layout Definition
Кольца
\begin_inset Foot
status open

\begin_layout Plain Layout
Некоторые математики определяют кольцо без нейтрального элемента по умножению
 и относящихся с нему аксиом, называя кольца, в которых они имеются унитарными
 кольцами.
 Мы такого различия проводить не будем.
\end_layout

\end_inset

 обладают свойствами, которые мы привыкли ассоциировать с целыми числами.
 Примерами являются:
\end_layout

\begin_layout Itemize
целые числа;
\end_layout

\begin_layout Itemize
множество матриц размерности 
\begin_inset Formula $n\times n$
\end_inset

 с вещественными коэффициентами;
\end_layout

\begin_layout Itemize
множество гауссовых целых чисел;
\end_layout

\begin_layout Itemize
множество многочленов с целыми коэффициентами.
\end_layout

\begin_layout Definition
Элемент 
\begin_inset Formula $x$
\end_inset

 кольца называется обратимым, если существует такой 
\begin_inset Formula $x^{-1}$
\end_inset

, что 
\begin_inset Formula 
\[
xx^{-1}=x^{-1}x=1.
\]

\end_inset


\end_layout

\begin_layout Standard
В каждом кольце есть по крайней мере один обратимый элемент — 1.
 Но их может быть и больше, например, в 
\begin_inset Formula $\mathbb{Z}$
\end_inset

 обратимы 
\begin_inset Formula $1$
\end_inset

 и 
\begin_inset Formula $-1$
\end_inset

.
\end_layout

\begin_layout Definition
\begin_inset Note Note
status open

\begin_layout Plain Layout
Какой смысл этого определения? Может быть избавиться от него и избежать
 путаницы?
\end_layout

\end_inset

Обратимый элемент кольца называется единицей этого кольца.
\end_layout

\begin_layout Problem
(очень лёгкое) Какое кольцо содержит в точности один обратимый элемент?
 Каковы единицы в кольце 
\begin_inset Formula $\mathbb{Z}\left[\sqrt{-1}\right]$
\end_inset

 гауссовых целых чисел?
\end_layout

\begin_layout Solution
Один обратимый элемент может быть только в кольце, состоящем из 
\begin_inset Formula $0$
\end_inset

 и 
\begin_inset Formula $1$
\end_inset

.
\end_layout

\begin_layout Solution
Гауссовы целые числа имеют вид 
\begin_inset Formula $m+in$
\end_inset

, где 
\begin_inset Formula $m,n\in\mathbb{Z}$
\end_inset

.
 
\begin_inset Formula 
\[
\frac{1}{m+in}=\frac{m-in}{m^{2}+n^{2}}=\frac{m}{m^{2}+n^{2}}-i\frac{n}{m^{2}+n^{2}}.
\]

\end_inset

 Если 
\begin_inset Formula $\left|m\right|>1$
\end_inset

, то 
\begin_inset Formula $m^{2}+n^{2}>m$
\end_inset

, поэтому 
\begin_inset Formula $m$
\end_inset

 не может делиться нацело на 
\begin_inset Formula $m^{2}+n^{2}$
\end_inset

.
 Аналогично 
\begin_inset Formula $n$
\end_inset

 не делиться нацело на 
\begin_inset Formula $m^{2}+n^{2}$
\end_inset

 при 
\begin_inset Formula $\left|n\right|>1$
\end_inset

.
 Поэтому у обратимого элемента 
\begin_inset Formula $\left|m\right|\le1$
\end_inset

 и 
\begin_inset Formula $\left|n\right|\le1$
\end_inset

.
 
\begin_inset Formula $0+i0$
\end_inset

 не является обратимым, так как 
\begin_inset Formula $0x=x0=0\neq1$
\end_inset

.
 Обратимыми являются 
\begin_inset Formula $\pm1$
\end_inset

 и 
\begin_inset Formula $\pm i$
\end_inset

.
 Ещё остаются элементы 
\begin_inset Formula $\pm1\pm i$
\end_inset

, но они не являются обратимыми, так как 
\begin_inset Formula $\pm1$
\end_inset

 не делиться на 
\begin_inset Formula $2$
\end_inset

.
\end_layout

\begin_layout Theorem
Множество единиц кольца замкнуто относительно умножения (то есть произведение
 двух единиц само является единицей).
\end_layout

\begin_layout Proof
Пусть 
\begin_inset Formula $a$
\end_inset

 и 
\begin_inset Formula $b$
\end_inset

 — единицы кольца 
\begin_inset Formula $R$
\end_inset

, то есть существуют 
\begin_inset Formula $a^{-1},b^{-1}\in R$
\end_inset

 такие, что 
\begin_inset Formula 
\[
aa^{-1}=a^{-1}a=bb^{-1}=b^{-1}b=1.
\]

\end_inset


\end_layout

\begin_layout Proof
Докажем, что у элемента 
\begin_inset Formula $ab$
\end_inset

 есть обратный элемент, а именно — 
\begin_inset Formula $b^{-1}a^{-1}$
\end_inset

.
 Действительно: 
\begin_inset Formula 
\[
\left(ab\right)\left(b^{-1}a^{-1}\right)=a\left(bb^{-1}\right)a^{-1}=a\cdot1\cdot a^{-1}=aa^{-1}=1,
\]

\end_inset


\begin_inset Formula 
\[
\left(b^{-1}a^{-1}\right)\left(ab\right)=b^{-1}\left(aa^{-1}\right)b=b^{-1}\cdot1\cdot b=b^{-1}b=1.
\]

\end_inset


\end_layout

\begin_layout Problem
Докажите, что
\end_layout

\begin_layout Problem
1) 
\begin_inset Formula $1$
\end_inset

 является единицей;
\end_layout

\begin_layout Problem
2) элемент, обратный единице, является единицей.
\end_layout

\begin_layout Solution
1) По определению 
\begin_inset Formula $1x=x1=x$
\end_inset

.
 Подставив в это равенство 
\begin_inset Formula $x=1$
\end_inset

, получим 
\begin_inset Formula 
\[
1\cdot1=1\cdot1=1,
\]

\end_inset

 то есть у 
\begin_inset Formula $1$
\end_inset

 есть обратный элемент, а именно — сама 
\begin_inset Formula $1$
\end_inset

, поэтому 
\begin_inset Formula $1$
\end_inset

 является единицей.
\end_layout

\begin_layout Solution
2) Пусть 
\begin_inset Formula $a$
\end_inset

 — единица, тогда существует такой 
\begin_inset Formula $b=a^{-1}$
\end_inset

, что 
\begin_inset Formula $ab=ba=1$
\end_inset

.
 Это равенство можно переписать следующим образом: 
\begin_inset Formula 
\[
ba=ab=1,
\]

\end_inset

откуда следует, что 
\begin_inset Formula $a=b^{-1}$
\end_inset

, то есть у 
\begin_inset Formula $a^{-1}$
\end_inset

 есть обратный элемент и это 
\begin_inset Formula $a$
\end_inset

.
\end_layout

\begin_layout Definition
Элемент 
\begin_inset Formula $x$
\end_inset

 кольца называется делителем нуля, если 
\begin_inset Formula $x\neq0$
\end_inset

 и существует такой 
\begin_inset Formula $y\neq0$
\end_inset

, что 
\begin_inset Formula $xy=0$
\end_inset

.
\end_layout

\begin_layout Standard
Например, в кольце 
\begin_inset Formula $\mathbb{Z}_{6}$
\end_inset

 элементы 
\begin_inset Formula $2$
\end_inset

 и 
\begin_inset Formula $3$
\end_inset

 являются делителями нуля.
\end_layout

\begin_layout Definition
Коммутативное кольцо без делителей нуля называется 
\emph on
областью целостности
\emph default
.
\end_layout

\begin_layout Standard
Примеры областей целостности:
\end_layout

\begin_layout Itemize
целые числа;
\end_layout

\begin_layout Itemize
гауссовы числа;
\end_layout

\begin_layout Itemize
многочлены над множеством целых чисел;
\end_layout

\begin_layout Itemize
рациональные функции над множеством целых чисел (рациональная функция —
 отношение двух полиномов).
\end_layout

\begin_layout Standard
Кольцо остатков будет областью целостности тогда и только тогда, когда модуль
 — простое число.
\end_layout

\begin_layout Problem
(очень лёгкое) Докажите, что делитель нуля не является единицей.
 Пусть 
\begin_inset Formula $x$
\end_inset

 — делитель нуля, тогда существует 
\begin_inset Formula $y\neq0$
\end_inset

 такой, что 
\begin_inset Formula 
\[
xy=0.
\]

\end_inset

 Если 
\begin_inset Formula $x$
\end_inset

 — единица, то существует 
\begin_inset Formula $x^{-1}$
\end_inset

 такой, что 
\begin_inset Formula $x^{-1}x=1$
\end_inset

, умножив это равенство справа на 
\begin_inset Formula $y$
\end_inset

, получим 
\begin_inset Formula 
\[
\left(x^{-1}x\right)y=1y,
\]

\end_inset

 слева применим ассоциативность, а справа — аксиому умножения на единицу:
 
\begin_inset Formula 
\[
x^{-1}\left(xy\right)=y,
\]

\end_inset

 так как 
\begin_inset Formula $xy=0$
\end_inset

, то получаем 
\begin_inset Formula 
\[
y=x^{-1}0=0,
\]

\end_inset

 но 
\begin_inset Formula $y\neq0$
\end_inset

, полученное противоречие означает, что 
\begin_inset Formula $x$
\end_inset

 — не является единицей.
\end_layout

\begin_layout Section
Умножение матриц и полукольца
\end_layout

\begin_layout Standard
\begin_inset Note Note
status open

\begin_layout Plain Layout
Рассмотреть операции с матрицами
\end_layout

\end_inset


\end_layout

\begin_layout Standard
Точно так же, как раньше мы обобщили функцию возведения в степень на произвольну
ю операцию, так теперь обобщим умножение матриц.
 Обычно мы рассматриваем умножение матриц как вычисление нескольких сумм
 произведений.
 Но с точки зрения математики важно лишь, чтобы были две операции: одна
 
\begin_inset Quotes rld
\end_inset

типа плюс
\begin_inset Quotes rrd
\end_inset

 — ассоциативная и коммутативная (обозначается 
\begin_inset Formula $\oplus$
\end_inset

), другая 
\begin_inset Quotes rld
\end_inset

типа умножить
\begin_inset Quotes rrd
\end_inset

 — ассоциативная (обозначает 
\begin_inset Formula $\otimes$
\end_inset

).
 Причём вторая операция должна быть дистрибутивна относительно первой: 
\begin_inset Formula 
\[
a\otimes\left(b\oplus c\right)=a\otimes b\oplus a\otimes c,
\]

\end_inset


\end_layout

\begin_layout Standard
\begin_inset Formula 
\[
\left(b\oplus c\right)\otimes a=b\otimes a\oplus c\otimes a.
\]

\end_inset


\end_layout

\begin_layout Standard
Чуть выше мы видели как раз такую алгебраическую структуру — 
\emph on
кольцо.

\emph default
 Однако требования, предъявляемые к кольцу, для нас чрезмерны, точнее, нам
 ни к чему обратная относительно сложения операция.
 Нам нужно всего лишь 
\emph on
полукольцо
\emph default
, кольцо без операции вычитания.
\end_layout

\begin_layout Definition

\emph on
Полукольцом 
\emph default
называется множество, на котором определены: операции 
\begin_inset Formula $x+y$
\end_inset

 и 
\begin_inset Formula $xy$
\end_inset

, константы 
\begin_inset Formula $0$
\end_inset

 и 
\begin_inset Formula $1$
\end_inset

, причём выполняются следующие аксиомы: 
\begin_inset Formula 
\[
x+\left(y+z\right)=\left(x+y\right)+z;
\]

\end_inset


\begin_inset Formula 
\[
x+0=0+x=x;
\]

\end_inset


\begin_inset Formula 
\[
x+y=y+x;
\]

\end_inset


\begin_inset Formula 
\[
x\left(yz\right)=\left(xy\right)z;
\]

\end_inset


\begin_inset Formula 
\[
1\neq0;
\]

\end_inset


\begin_inset Formula 
\[
1x=x1=x;
\]

\end_inset


\begin_inset Formula 
\[
0x=x0=0;
\]

\end_inset


\begin_inset Formula 
\[
x\left(y+z\right)=xy+xz;
\]

\end_inset


\begin_inset Formula 
\[
\left(y+z\right)x=yx+zx.
\]

\end_inset


\end_layout

\begin_layout Standard
Канонический пример полукольца — множество натуральных чисел.
 Хотя для натуральных чисел не определено обращение операций сложения, матрицы
 с целыми неотрицательными коэффициентами вполне можно перемножать (на самом
 деле можно было бы ещё ослабить требования, исключив нейтральные относительно
 сложения и умножения элементы и относящиеся к ним аксиомы, матричное умножение
 все равно будет определено корректно
\begin_inset Foot
status open

\begin_layout Plain Layout
Здесь предполагается прямолинейный алгоритм умножения матриц; для быстрых
 алгоритмов необходимы более сильные теории
\end_layout

\end_inset

.
 Полукольцо без 0 и 1 можно было бы назвать 
\emph on
слабым полукольцом.
\emph default
)
\end_layout

\begin_layout Section
Приложения: социальные сети и кратчайшие пути
\end_layout

\begin_layout Standard
\begin_inset Tabular
<lyxtabular version="3" rows="8" columns="8">
<features tabularvalignment="middle">
<column alignment="center" valignment="top">
<column alignment="center" valignment="top">
<column alignment="center" valignment="top">
<column alignment="center" valignment="top">
<column alignment="center" valignment="top">
<column alignment="center" valignment="top">
<column alignment="center" valignment="top">
<column alignment="center" valignment="top">
<row>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Ari
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Bev
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Cal
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Don
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Eva
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Fay
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Gia
\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Ari
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
1
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
1
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
0
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
1
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
0
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
0
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
0
\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Bev
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
1
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
1
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
0
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
0
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
0
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
1
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
0
\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Cal
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
0
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
0
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
1
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
1
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
0
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
0
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
0
\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Don
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
1
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
0
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
1
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
1
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
0
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
1
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
0
\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Eva
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
0
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
0
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
0
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
0
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
1
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
0
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
1
\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Fay
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
0
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
1
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
0
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
1
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
0
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
1
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
0
\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Gia
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
0
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
0
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
0
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
0
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
1
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
0
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
1
\end_layout

\end_inset
</cell>
</row>
</lyxtabular>

\end_inset


\end_layout

\begin_layout Standard
\begin_inset Note Note
status open

\begin_layout Plain Layout
Определение булевого полукольца
\end_layout

\end_inset


\end_layout

\begin_layout Problem
Применяя алгоритм возведения в степень из главы 7 к умножению матриц над
 булевым полукольцом, напишите функцию построения транзитивного замыкания
 графа.
 Воспользуйтесь этой функцией для нахождения социальной сети каждого человека
 в таблице.
\end_layout

\begin_layout Solution
\begin_inset Note Note
status open

\begin_layout Plain Layout
Написать решение
\end_layout

\end_inset


\end_layout

\begin_layout Standard
В этом случае мы воспользуемся матричным умножением, порождаемым тропическим
 или 
\begin_inset Formula $\left\{ \min;+\right\} $
\end_inset

-полукольцом:
\begin_inset Formula 
\[
b_{ij}=\min_{k=1,\dots,n}\left(a_{ik}+a_{kj}\right).
\]

\end_inset


\end_layout

\begin_layout Problem
Применяя алгоритм возведения в степень из главы 7 к умножению матриц над
 тропическим полукольцом, напишите программу нахождения длины кратчайшего
 пути в графе.
\end_layout

\begin_layout Solution
\begin_inset Note Note
status open

\begin_layout Plain Layout
Написать решение
\end_layout

\end_inset


\end_layout

\begin_layout Problem
Модифицируйте программу из упражнения 8.8 так, чтобы она возвращала не только
 длину кратчайшего пути, но и сам кратчайший путь (последовательность рёбер).
\end_layout

\begin_layout Solution
\begin_inset Note Note
status open

\begin_layout Plain Layout
Написать решение
\end_layout

\end_inset


\end_layout

\begin_layout Section
Евклидовы кольца
\end_layout

\begin_layout Standard
Мы начали эту главу с обобщения алгоритма Евклида нахождения НОД сначала
 на полиномы, затем на комплексные числа и т.д.
 Как далеко может завести такое обобщение? Иными словами, каковы самые общие
 математические сущности, для которых работает алгоритм вычисления НОД (область
 определения алгоритма)? Разработанные Нётер абстракции наконец-то позволили
 найти ответ на этот вопрос: область определения алгоритма вычисления НОД
 Нётер назвала 
\emph on
евклидовым кольцом
\emph default
.
\end_layout

\begin_layout Definition
Множество 
\begin_inset Formula $E$
\end_inset

 называется 
\emph on
евклидовым кольцом
\emph default
, если: 
\begin_inset Formula $E$
\end_inset

 — область целостности и в 
\begin_inset Formula $E$
\end_inset

 определены операции 
\begin_inset Formula $quotient$
\end_inset

 и 
\begin_inset Formula $reminder$
\end_inset

 такие, что 
\begin_inset Formula 
\[
b\neq0\Rightarrow a=quotient(a,b)\cdot b+remainder(a,b);
\]

\end_inset

в 
\begin_inset Formula $E$
\end_inset

 определена неотрицательная норма 
\begin_inset Formula $\left\Vert x\right\Vert :E\to\mathbb{N}$
\end_inset

, удовлетворяющая следующим условиям:
\begin_inset Formula 
\[
\begin{array}{c}
\left\Vert a\right\Vert =0\Rightarrow a=0,\\
b\neq0\rightarrow\left\Vert ab\right\Vert \ge\left\Vert a\right\Vert ,\\
\left\Vert remainder\left(a,b\right)\right\Vert <\left\Vert b\right\Vert .
\end{array}
\]

\end_inset


\end_layout

\begin_layout Standard
Используемую здесь норму не следует путать с нормой линейных нормированных
 пространств, изучаемых в линейной алгебре.
\end_layout

\begin_layout Standard
Чтобы обобщить нечто, не нужно добавлять новые сущности.
 Нужно убрать ограничения и свести алгоритм к самой сути.
\end_layout

\begin_layout Section
Поля и другие алгебраические структуры
\end_layout

\begin_layout Standard
Ещё одна важная абстракция — поле
\begin_inset Foot
status open

\begin_layout Plain Layout
Термин 
\begin_inset Quotes rld
\end_inset

поле
\begin_inset Quotes rrd
\end_inset

 этимологически связан с полем для исследований, а не с пшеничным полем
\end_layout

\end_inset

.
\end_layout

\begin_layout Definition
Область целостности, в которой каждый ненулевой элемент обратим, называется
 
\emph on
полем
\emph default
.
\end_layout

\begin_layout Standard
Если каноническим примером кольца являются целые числа, то каноническим
 примером поля — рациональные числа 
\begin_inset Formula $\mathbb{Q}$
\end_inset

.
 Ещё несколько примеров: вещественные числа, поле остатков по простому модулю
 
\begin_inset Formula $\mathbb{Z}_{p}$
\end_inset

, комплексные числа.
\end_layout

\begin_layout Standard
Простым полем называется поле, не содержащее нетривиального подполя (не
 совпадающего с самим полем).
 Как выясняется, у любого поля есть только одно из двух видов простых подполей:
 
\begin_inset Formula $\mathbb{Q}$
\end_inset

 или 
\begin_inset Formula $\mathbb{Z}_{p}$
\end_inset

.
 Характеристика поля равна 
\begin_inset Formula $p$
\end_inset

, если его простое подполе совпадает с 
\begin_inset Formula $\mathbb{Z}_{p}$
\end_inset

, если же оно совпадает с 
\begin_inset Formula $\mathbb{Q}$
\end_inset

, то характеристика равна 
\begin_inset Formula $0$
\end_inset

.
\end_layout

\begin_layout Standard
Любое поле можно получить, начав с простого поля и добавляя элементы с соблюдени
ем аксиом поля.
 Это называется расширением поля.
 В частности, поле можно алгебраически расширить, добавив дополнительный
 элемент, являющийся корнем некоторого полинома.
 Например, можно расширить поле 
\begin_inset Formula $\mathbb{Q}$
\end_inset

 элементом 
\begin_inset Formula $\sqrt{2}$
\end_inset

, не являющимся рациональным числом, поскольку это корень полинома 
\begin_inset Formula $x^{2}-2$
\end_inset

.
\end_layout

\begin_layout Standard
Можно также расширить поле 
\emph on
топологически
\emph default
, 
\begin_inset Quotes rld
\end_inset

заполнив дыры
\begin_inset Quotes rrd
\end_inset

.
 Рациональные числа оставляют лакуны на числовой оси, но у вещественных
 чисел лакун нет, поэтому поле вещественных чисел является топологическим
 расширением поля рациональных чисел.
 Можно также расширить это поле на два измерения с помощью комплексных чисел.
 Удивительно, но других конечномерных полей, содержащих вещественные числа,
 не существует
\begin_inset Foot
status open

\begin_layout Plain Layout
Существуют похожи на поля четырехмерные и восьмимерные струтуры, которые
 называются кватернионами и октонионами.
 Но это не совсем поля, потому что они не удовлетворяют некоторым аксиомам:
 они не коммутативны по умножению, а умножение октонионов ещё и не ассоциативно.
 Других конечномерных расширений поля вещественных чисел не существует.
\end_layout

\end_inset

.
\end_layout

\begin_layout Standard
Все рассмотренные до сих пор алгебраические структуры стороились над одним
 множеством значений, но существуют также структуры, определённые над нескольким
и множествами.
 Например, важная структура, именуемая 
\emph on
модулем
\emph default
, содержит главное множество (аддитивную группу 
\begin_inset Formula $G$
\end_inset

) и вспомогательное множество (кольцо коэффициентов 
\begin_inset Formula $R$
\end_inset

) с дополнительной операцией 
\begin_inset Formula $R\times G\to G$
\end_inset

, которая удовлетворяет следующим аксиомам: 
\begin_inset Formula 
\begin{multline*}
a,b\in R\wedge x,y\in G:\\
\begin{array}{c}
\left(a+b\right)x=ax+bx,\\
a\left(x+y\right)=ax+ay.
\end{array}
\end{multline*}

\end_inset


\end_layout

\begin_layout Standard
Если кольцо 
\begin_inset Formula $R$
\end_inset

 является ещё и полем, то такая структура называется 
\emph on
векторным пространством
\emph default
.
\end_layout

\begin_layout Section
Заключительные мысли
\end_layout

\begin_layout Standard
\begin_inset Tabular
<lyxtabular version="3" rows="8" columns="5">
<features tabularvalignment="middle">
<column alignment="center" valignment="top">
<column alignment="center" valignment="top">
<column alignment="center" valignment="top">
<column alignment="center" valignment="top">
<column alignment="center" valignment="top">
<row>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Структура
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Операции
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Элементы
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Аксиомы
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Пример
\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Магма
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $x\circ y$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Полугруппа
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $x\circ y$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $x\circ\left(y\circ z\right)=\left(x\circ y\right)\circ z$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $\left(\mathbb{Z^{+}},+\right)$
\end_inset


\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Моноид
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $x\circ y$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $e$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $\begin{array}{c}
x\circ\left(y\circ z\right)=\left(x\circ y\right)\circ z\\
x\circ e=e\circ x=x
\end{array}$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Строки с операцией конкатенации
\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Группа
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $x\circ y,x^{-1}$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $e$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $\begin{array}{c}
x\circ\left(y\circ z\right)=\left(x\circ y\right)\circ z\\
x\circ e=e\circ x=x\\
x\circ x^{-1}=x^{-1}\circ x=e
\end{array}$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Обратимые матрицы с операцией умножения
\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Абелева группа
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $x\circ y,x^{-1}$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $e$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $\begin{array}{c}
x\circ\left(y\circ z\right)=\left(x\circ y\right)\circ z\\
x\circ e=e\circ x=x\\
x\circ x^{-1}=x^{-1}\circ x=e\\
x\circ y=y\circ x
\end{array}$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Двумерные векторы с операцией сложения
\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Полукольцо
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $x+y,xy$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $0$
\end_inset

, 
\begin_inset Formula $1$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $\begin{array}{c}
x+\left(y+z\right)=\left(x+y\right)+z\\
x+0=0+x=x\\
x+y=y+x\\
x\left(yz\right)=\left(xy\right)z\\
1\neq0\\
1x=x1=x\\
0x=x0=0\\
x\left(y+z\right)=xy+xz\\
\left(y+z\right)x=yx+zx
\end{array}$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Натуральные числа
\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Кольцо
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $x+y,xy,-x$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $0$
\end_inset

, 
\begin_inset Formula $1$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $\begin{array}{c}
x+\left(y+z\right)=\left(x+y\right)+z\\
x+0=0+x=x\\
x+\left(-x\right)=\left(-x\right)+x=0\\
x+y=y+x\\
x\left(yz\right)=\left(xy\right)z\\
1\neq0\\
1x=x1=x\\
0x=x0=0\\
x\left(y+z\right)=xy+xz\\
\left(y+z\right)x=yx+zx
\end{array}$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Целые числа
\end_layout

\end_inset
</cell>
</row>
</lyxtabular>

\end_inset


\end_layout

\begin_layout Chapter
Организация математических знаний
\end_layout

\begin_layout Section
Доказательства
\end_layout

\begin_layout Standard
\begin_inset Note Note
status open

\begin_layout Plain Layout
Наглядное доказательство: 
\begin_inset Formula $a+b=b+a$
\end_inset


\end_layout

\end_inset


\end_layout

\begin_layout Standard
\begin_inset Note Note
status open

\begin_layout Plain Layout
Наглядное доказательство: 
\begin_inset Formula $\left(a+b\right)+c=a+\left(b+c\right)$
\end_inset


\end_layout

\end_inset


\end_layout

\begin_layout Standard
\begin_inset Note Note
status open

\begin_layout Plain Layout
Наглядное доказательство: 
\begin_inset Formula $ab=ba$
\end_inset


\end_layout

\end_inset


\end_layout

\begin_layout Standard
\begin_inset Note Note
status open

\begin_layout Plain Layout
Наглядное доказательство: 
\begin_inset Formula $\left(ab\right)c=a\left(bc\right)$
\end_inset


\end_layout

\end_inset


\end_layout

\begin_layout Standard
\begin_inset Note Note
status open

\begin_layout Plain Layout
Наглядное доказательство: 
\begin_inset Formula $\left(a+b\right)^{2}=a^{2}+2ab+b^{2}$
\end_inset


\end_layout

\end_inset


\end_layout

\begin_layout Standard
\begin_inset Note Note
status open

\begin_layout Plain Layout
Наглядное доказательство: 
\begin_inset Formula $\pi>3$
\end_inset


\end_layout

\end_inset


\end_layout

\begin_layout Problem
Придумайте наглядные доказательства следующих тождеств:
\end_layout

\begin_layout Problem
\begin_inset Formula $\left(a-b\right)^{2}=a^{2}-2ab+b^{2},$
\end_inset


\end_layout

\begin_layout Problem
\begin_inset Formula $a^{2}-b^{2}=\left(a+b\right)\left(a-b\right),$
\end_inset


\end_layout

\begin_layout Problem
\begin_inset Formula $\left(a+b\right)^{3}=a^{3}+3a^{2}b+3ab^{2}+b^{3},$
\end_inset


\end_layout

\begin_layout Problem
\begin_inset Formula $\left(a-b\right)^{3}=a^{3}-3a^{2}b+3ab^{2}-b^{3}.$
\end_inset


\end_layout

\begin_layout Solution
\begin_inset Note Note
status open

\begin_layout Plain Layout
Написать решение.
 Нужно придумать, как эффективно строить чертежи
\end_layout

\end_inset


\end_layout

\begin_layout Problem
С помощью наглядного доказательства найдите верхнюю границу 
\begin_inset Formula $\pi$
\end_inset

.
\end_layout

\begin_layout Solution
\begin_inset Note Note
status open

\begin_layout Plain Layout
Написать решение и построить чертёж.
 Идея: вписать круг в квадрат
\end_layout

\end_inset


\end_layout

\begin_layout Definition

\emph on
Доказательство 
\emph default
предложения обладает следующими свойствами: 
\end_layout

\begin_layout Definition
1) это рассуждение;
\end_layout

\begin_layout Definition
2) оно принято математическим сообществом;
\end_layout

\begin_layout Definition
3) оно устанавливает истинность предложения.
\end_layout

\begin_layout Section
Первая теорема
\end_layout

\begin_layout Theorem
(теорема Фалеса).
 Для любого вписанного в круг треугольника, опирающегося на её диаметр,
 угол при вершине, противположной диаметру, является прямым.
\end_layout

\begin_layout Proof
\begin_inset Note Note
status open

\begin_layout Plain Layout
Написать доказательство.
 Нужно средство построения чертежей
\end_layout

\end_inset


\end_layout

\begin_layout Section
Евклид и аксиоматический метод
\end_layout

\begin_layout Standard
\begin_inset Note Comment
status open

\begin_layout Plain Layout
Раздел не содержит определений, теорем и задач
\end_layout

\end_inset


\end_layout

\begin_layout Section
Альтернативы евклидовой геометрии
\end_layout

\begin_layout Standard
\begin_inset Note Comment
status open

\begin_layout Plain Layout
Раздел не содержит определений, теорем и задач
\end_layout

\end_inset


\end_layout

\begin_layout Section
Формалистический подход Гильберта
\end_layout

\begin_layout Standard
\begin_inset Note Comment
status open

\begin_layout Plain Layout
Раздел не содержит определений, теорем и задач
\end_layout

\end_inset


\end_layout

\begin_layout Section
Пеано и его аксиомы
\end_layout

\begin_layout Standard
\begin_inset Note Comment
status open

\begin_layout Plain Layout
Раздел не содержит определений, теорем и задач
\end_layout

\end_inset


\end_layout

\begin_layout Standard
В 1889 году Пеано опубликовал набор аксиом, заложивших формальную основу
 арифметики.
 Их было пять, как и у Евклида/
\end_layout

\begin_layout Standard
Существует множество 
\begin_inset Formula $\mathbb{N}$
\end_inset

, называемое множеством 
\emph on
натуральных чисел
\emph default
:
\end_layout

\begin_layout Enumerate
\begin_inset Formula $\exists0\in\mathbb{N}.$
\end_inset


\end_layout

\begin_layout Enumerate
\begin_inset Formula $\forall n\in\mathbb{N}:\exists n^{\prime}\in\mathbb{N}$
\end_inset

 — следующий элемент.
\end_layout

\begin_layout Enumerate
\begin_inset Formula $\forall S\subset\mathbb{N}:\left(0\in S\wedge\forall n:n\in S\Rightarrow n^{\prime}\in S\right)\Rightarrow S=\mathbb{N}.$
\end_inset


\end_layout

\begin_layout Enumerate
\begin_inset Formula $\forall n,m\in\mathbb{N}:n^{\prime}=m^{\prime}\Rightarrow n=m.$
\end_inset


\end_layout

\begin_layout Enumerate
\begin_inset Formula $\forall n\in\mathbb{N}:n^{\prime}\neq0.$
\end_inset


\end_layout

\begin_layout Standard
\begin_inset Note Note
status open

\begin_layout Plain Layout
Доказать необходимость всех аксиом.
 Полезнее будет не переписывать это, а вернуться к этому и доказать самостоятель
но
\end_layout

\end_inset


\end_layout

\begin_layout Section
Построение арифметики
\end_layout

\begin_layout Standard
\begin_inset Note Note
status open

\begin_layout Plain Layout
Разбить на более формальные блоки
\end_layout

\end_inset


\end_layout

\begin_layout Standard
Установив, что все аксиомы Пеана независимы и, стал быть, необходимы для
 описания того, что понимается под целыми числами, мы можем построить арифметику
 на чисто теоретической основе.
 Для этого мы точно определим, что понимать под сложением и умножением двух
 натуральных чисел:
\end_layout

\begin_layout Standard
\begin_inset Formula 
\begin{equation}
a+0=a,\label{eq:peano-plus-zero}
\end{equation}

\end_inset


\begin_inset Formula 
\begin{equation}
a+b^{\prime}=\left(a+b\right)^{\prime}.\label{eq:peano-plus-successor}
\end{equation}

\end_inset


\end_layout

\begin_layout Standard
Мы не доказываем эти утверждения, они составляют само определение сложения.
 Из этого определения следуют все свойства сложения натуральных чисел.
\end_layout

\begin_layout Standard
Докажем, что 
\begin_inset Formula $0$
\end_inset

 — левый нейтральный элемент относительно сложения, то есть, что для любого
 
\begin_inset Formula $0+a=a$
\end_inset

.
 Докажем это утверждение по индукции.
 База индукции: 
\begin_inset Formula $0+0=0$
\end_inset

 является верным утверждением в силу 
\begin_inset CommandInset ref
LatexCommand ref
reference "eq:peano-plus-zero"
plural "false"
caps "false"
noprefix "false"

\end_inset

 при 
\begin_inset Formula $a=0$
\end_inset

.
\end_layout

\begin_layout Standard
Теперь нужно доказать, что из 
\begin_inset Formula $0+a=a$
\end_inset

 следует 
\begin_inset Formula $0+a^{\prime}=a^{\prime}$
\end_inset

.
 Действительно, по определению сложения 
\begin_inset CommandInset ref
LatexCommand ref
reference "eq:peano-plus-successor"
plural "false"
caps "false"
noprefix "false"

\end_inset

: 
\begin_inset Formula $0+a^{\prime}=\left(0+a\right)^{\prime}$
\end_inset

.
 По предположению индукции 
\begin_inset Formula $0+a=a$
\end_inset

, поэтому 
\begin_inset Formula 
\[
0+a^{\prime}=\left(0+a\right)^{\prime}=a^{\prime},
\]

\end_inset

 что и требовалось.
\end_layout

\begin_layout Standard
Определение умножения: 
\begin_inset Formula 
\begin{equation}
a\cdot0=0,\label{eq:peano-mult-zero}
\end{equation}

\end_inset


\begin_inset Formula 
\begin{equation}
a\cdot b^{\prime}=\left(a\cdot b\right)+a.\label{eq:peano-mult-successor}
\end{equation}

\end_inset


\end_layout

\begin_layout Standard
Теперь мы можем доказать, что 
\begin_inset Formula $0\cdot a=0$
\end_inset

.
 Сделаем это с помощью метода математической индукции.
\end_layout

\begin_layout Standard
База индукции: при 
\begin_inset Formula $a=0$
\end_inset

 из 
\begin_inset CommandInset ref
LatexCommand ref
reference "eq:peano-mult-zero"
plural "false"
caps "false"
noprefix "false"

\end_inset

 получаем 
\begin_inset Formula $0\cdot0=0$
\end_inset

.
\end_layout

\begin_layout Standard
Шаг индукции: 
\begin_inset Formula $0\cdot a=0\Rightarrow0\cdot a^{\prime}=0\cdot a+0=0+0=0.$
\end_inset


\end_layout

\begin_layout Standard
Определим 
\begin_inset Formula $1$
\end_inset

 как число, следующее за 
\begin_inset Formula $0$
\end_inset

: 
\begin_inset Formula $0^{\prime}=1$
\end_inset

.
 Мы знаем, как прибавить 1:
\end_layout

\begin_layout Standard
\begin_inset Formula 
\[
a+1=a+0^{\prime}=\left(a+0\right)^{\prime}=a^{\prime}.
\]

\end_inset


\end_layout

\begin_layout Standard
Мы также знаем, как умножить на 1: 
\begin_inset Formula 
\[
a\cdot1=a\cdot0^{\prime}=\left(a\cdot0\right)+a=a.
\]

\end_inset


\end_layout

\begin_layout Standard
Докажем ассоциативность сложения: 
\begin_inset Formula $\left(a+b\right)+c=a+\left(b+c\right)$
\end_inset

 индукцией по 
\begin_inset Formula $c$
\end_inset

.
\end_layout

\begin_layout Standard
База индукции: 
\begin_inset Formula $\left(a+b\right)+0=a+b$
\end_inset

, 
\begin_inset Formula $a+\left(b+0\right)=a+b$
\end_inset

, поэтому 
\begin_inset Formula $\left(a+b\right)+0=a+\left(b+0\right)$
\end_inset

.
\end_layout

\begin_layout Standard
Шаг индукции: пусть 
\begin_inset Formula $\left(a+b\right)+c=a+\left(b+c\right)$
\end_inset

, тогда 
\begin_inset Formula 
\[
\left(a+b\right)+c^{\prime}=\left(\left(a+b\right)+c\right)^{\prime}=\left(a+\left(b+c\right)\right)^{\prime}
\]

\end_inset

 и 
\begin_inset Formula 
\[
a+\left(b+c^{\prime}\right)=a+\left(b+c\right)^{\prime}=\left(a+\left(b+c\right)\right)^{\prime}.
\]

\end_inset


\end_layout

\begin_layout Standard
Так как правые части последних двух равенств равны, то равны и левые: 
\begin_inset Formula 
\[
\left(a+b\right)+c^{\prime}=a+\left(b+c^{\prime}\right),
\]

\end_inset

 что и требовалось.
\end_layout

\begin_layout Standard
Докажем теперь коммутативность сложения: 
\begin_inset Formula $a+b=b+a$
\end_inset

.
 При 
\begin_inset Formula $b=0$
\end_inset

 мы видели, что 
\begin_inset Formula $a+0=a$
\end_inset

 и 
\begin_inset Formula $0+a=a$
\end_inset

, поэтому действительно 
\begin_inset Formula $a+0=0+a$
\end_inset

.
\end_layout

\begin_layout Standard
Теперь нужно доказать, что из 
\begin_inset Formula $a+b=b+a$
\end_inset

 следует 
\begin_inset Formula $a+b^{\prime}=b^{\prime}+a$
\end_inset

.
 Выше мы видели, что 
\begin_inset Formula $b^{\prime}=b+1$
\end_inset

.
 Докажем, что 
\begin_inset Formula $b+1=1+b$
\end_inset

 по индукции.
\end_layout

\begin_layout Standard
База индукции: 
\begin_inset Formula $0+1=1=1+0$
\end_inset

.
\end_layout

\begin_layout Standard
Шаг индукции: Пусть 
\begin_inset Formula $b+1=1+b$
\end_inset

.
 Тогда, то по определению сложения: 
\end_layout

\begin_layout Standard
\begin_inset Formula 
\[
1+b^{\prime}=\left(1+b\right)^{\prime},
\]

\end_inset

 а по предположению 
\end_layout

\begin_layout Standard
\begin_inset Formula 
\[
1+b^{\prime}=\left(1+b\right)^{\prime}=\left(b+1\right)^{\prime}=\left(b+1\right)+1.
\]

\end_inset

 С другой стороны 
\begin_inset Formula $b^{\prime}+1=\left(b+1\right)+1$
\end_inset

.
 Так как правые части равенств равны, то равны и левые, то есть 
\begin_inset Formula 
\[
1+b^{\prime}=b^{\prime}+1,
\]

\end_inset

 то есть для любого 
\begin_inset Formula $b$
\end_inset

 имеет место 
\begin_inset Formula $1+b=b+1$
\end_inset

.
\end_layout

\begin_layout Standard
Пусть теперь 
\begin_inset Formula $a+b=b+a$
\end_inset

, докажем, что 
\begin_inset Formula $a+b^{\prime}=b^{\prime}+a$
\end_inset

.
 По определению сложения 
\begin_inset Formula $a+b^{\prime}=a+\left(b+1\right)$
\end_inset

, тогда, так как сложение ассоциативно и по предположению индукции
\begin_inset Formula 
\[
a+b^{\prime}=a+\left(b+1\right)=\left(a+b\right)+1=\left(b+a\right)+1.
\]

\end_inset


\end_layout

\begin_layout Standard
С другой стороны 
\begin_inset Formula $b^{\prime}+a=\left(b+1\right)+a$
\end_inset

.
 Так как сложение ассоциативно, то 
\begin_inset Formula 
\[
b^{\prime}+a=\left(b+1\right)+a=b+\left(1+a\right).
\]

\end_inset

 Выше мы показали, что сложение с 
\begin_inset Formula $1$
\end_inset

 коммутативно, поэтому 
\begin_inset Formula 
\[
b^{\prime}+a=b+\left(a+1\right).
\]

\end_inset

 Снова воспользуемся ассоциативностью сложения: 
\begin_inset Formula 
\[
b^{\prime}+a=b+\left(a+1\right)=\left(b+a\right)+1.
\]

\end_inset


\end_layout

\begin_layout Standard
Таким образом: 
\begin_inset Formula 
\[
a+b^{\prime}=\left(b+a\right)+1=b^{\prime}+a.
\]

\end_inset


\end_layout

\begin_layout Problem
По индукции докажите ассоциативность и коммутативность умножения, дистрибутивнос
ть умножения относительно сложения.
\end_layout

\begin_layout Solution
Докажем дистрибутивность умножения, то есть равенства 
\begin_inset Formula $a\left(b+c\right)=ab+ac$
\end_inset

 и 
\begin_inset Formula $\left(a+b\right)c=ac+bc$
\end_inset

.
 Доказательство проведём индукцией по 
\begin_inset Formula $c$
\end_inset

.
\end_layout

\begin_layout Solution
База индукции: По определению сложения 
\begin_inset Formula $a\left(b+0\right)=ab$
\end_inset

, с другой стороны: 
\begin_inset Formula $ab+a0=ab+0=ab$
\end_inset

, поэтому 
\begin_inset Formula $a\left(b+0\right)=ab+a0$
\end_inset

.
\end_layout

\begin_layout Solution
Шаг индукции: пусть 
\begin_inset Formula $a\left(b+c\right)=ab+ac$
\end_inset

, тогда 
\begin_inset Formula 
\[
a\left(b+c^{\prime}\right)=a\left(b+c\right)^{\prime}=a\left(b+c\right)+a=ab+ac+a.
\]

\end_inset


\end_layout

\begin_layout Solution
Заметим, что по определению умножения: 
\end_layout

\begin_layout Solution
\begin_inset Formula 
\[
ac^{\prime}=ac+a,
\]

\end_inset

поэтому
\begin_inset Formula 
\[
a\left(b+c^{\prime}\right)=ab+ac+a=ab+ac^{\prime},
\]

\end_inset

 что и требовалось.
\end_layout

\begin_layout Solution
Докажем второе равенство — 
\begin_inset Formula $\left(a+b\right)c=ac+bc$
\end_inset

 — индукцией по 
\begin_inset Formula $c$
\end_inset

.
\end_layout

\begin_layout Solution
База индукции: По определению умножения 
\begin_inset Formula $\left(a+b\right)0=0$
\end_inset

 и 
\begin_inset Formula $a0+b0=0+0=0$
\end_inset

, то есть 
\begin_inset Formula $\left(a+b\right)0=a0+b0$
\end_inset

.
\end_layout

\begin_layout Solution
Шаг индукции: Пусть 
\begin_inset Formula $\left(a+b\right)c=ac+bc$
\end_inset

.
 Тогда 
\begin_inset Formula $\left(a+b\right)c^{\prime}=\left(a+b\right)c+\left(a+b\right)=ac+bc+a+b$
\end_inset

.
 Так как сложение ассоциативно и коммутативно, то 
\begin_inset Formula 
\[
\left(a+b\right)c^{\prime}=\left(ac+a\right)+\left(bc+b\right),
\]

\end_inset

выше мы видели, что 
\begin_inset Formula $ac+a=ac^{\prime}$
\end_inset

, поэтому 
\begin_inset Formula 
\[
\left(a+b\right)c^{\prime}=ac^{\prime}+bc^{\prime},
\]

\end_inset

 что и требовалось.
\end_layout

\begin_layout Solution
Докажем ассоциативность умножения 
\begin_inset Formula $\left(ab\right)c=a\left(bc\right)$
\end_inset

 индукцией по 
\begin_inset Formula $c$
\end_inset

.
\end_layout

\begin_layout Solution
База индукции (при 
\begin_inset Formula $c=0)$
\end_inset

: По определению умножения 
\begin_inset Formula $\left(ab\right)0=0$
\end_inset

, с другой — 
\begin_inset Formula $a\left(b0\right)=a0=0$
\end_inset

, таким образом: 
\begin_inset Formula $\left(ab\right)0=a\left(b0\right)$
\end_inset

.
\end_layout

\begin_layout Solution
Шаг индукции: пусть 
\begin_inset Formula $\left(ab\right)c=a\left(bc\right)$
\end_inset

, тогда по определению умножения 
\begin_inset Formula $\left(ab\right)c^{\prime}=\left(ab\right)c+ab$
\end_inset

.
 С другой стороны 
\begin_inset Formula $a\left(bc^{\prime}\right)=a\left(\left(bc\right)+b\right)$
\end_inset

.
 так как умножение дистрибутивно относительно сложения: 
\begin_inset Formula 
\[
a\left(bc^{\prime}\right)=a\left(\left(bc\right)+b\right)=a\left(bc\right)+ab,
\]

\end_inset

 по предположению 
\begin_inset Formula $\left(ab\right)c=a\left(bc\right)$
\end_inset

, поэтому 
\begin_inset Formula 
\[
a\left(bc^{\prime}\right)=a\left(bc\right)+ab=\left(ab\right)c+ab=\left(ab\right)c^{\prime},
\]

\end_inset

 что и требовалось.
\end_layout

\begin_layout Standard
Наконец, докажем коммутативность умножения, то есть равенство 
\begin_inset Formula $ab=ba$
\end_inset

.
 Воспользуемся методом индукции по 
\begin_inset Formula $b$
\end_inset

.
 
\end_layout

\begin_layout Standard
База индукции: при 
\begin_inset Formula $b=0$
\end_inset

 получаем 
\begin_inset Formula $ab=a0=0$
\end_inset

 (по определению умножения) и 
\begin_inset Formula $ba=0a=0$
\end_inset

 (было доказано выше).
\end_layout

\begin_layout Standard
Шаг индукции: пусть 
\begin_inset Formula $ab=ba$
\end_inset

, по определению умножения 
\begin_inset Formula $ab^{\prime}=ab+a$
\end_inset

.
 По предположению шага индукции: 
\begin_inset Formula 
\[
ab^{\prime}=ab+a=ba+a,
\]

\end_inset

 а так как умножение дистрибутивно относительно сложения: 
\begin_inset Formula 
\[
ab^{\prime}=ba+a=\left(b+1\right)a=b^{\prime}a,
\]

\end_inset

 что и требовалось.
\end_layout

\begin_layout Problem
Пользуясь индукцией, определите полный порядок на множестве натуральных
 чисел.
\end_layout

\begin_layout Solution
Естественным полным порядком на множестве натуральных чисел является тот,
 который связан с понятием следующего элемента.
 Для каждого элемента 
\begin_inset Formula $a\in\mathbb{N}$
\end_inset

 определим, что 
\begin_inset Formula $a<a^{\prime}$
\end_inset

, а затем возьмём транзитивное замыкание этого отношения, то есть 
\begin_inset Formula $a<b\Rightarrow a<b^{\prime}$
\end_inset

 и 
\begin_inset Formula $a^{\prime}<b\Rightarrow a<b$
\end_inset

.
\end_layout

\begin_layout Problem
Пользуясь индукцией, определите полный частичную функцию 
\begin_inset Quotes rld
\end_inset

предшественник
\begin_inset Quotes rrd
\end_inset

 на множестве натуральных чисел.
\end_layout

\begin_layout Solution
Определение должно опираться на понятие следующего элемента.
 Предшественник и последующий элемент должны быть обратными операциями:
 
\begin_inset Formula $\left[p\left(a\right)\right]^{\prime}=p\left(a^{\prime}\right)=a$
\end_inset

.
 Для 
\begin_inset Formula $0$
\end_inset

 предшественника определить нельзя, поэтому первым будет 
\begin_inset Formula $p\left(1\right)=0$
\end_inset

.
\end_layout

\begin_layout Chapter
Основные понятия программирования
\end_layout

\begin_layout Section
Аристотель и абстракции
\end_layout

\begin_layout Standard
Аристотель ввёл понятие абстракции.
 Он описал различия между индивидуальным, видовым и родовым.
 Вид включает все 
\begin_inset Quotes rld
\end_inset

существенные
\begin_inset Quotes rrd
\end_inset

 свойства типа вещей.
 Род может содержать несколько видов, каждый из которых характеризуется
 
\emph on
отличительными свойствами
\emph default
 — признаками, которые отличают его от других видов в роде.
\end_layout

\begin_layout Standard
Именно аристотелева идея рода и лежит в основе термина 
\emph on
обобщённое программирование
\emph default
 — это способ рассуждать о программировании на уровне родовых, а не видовых
 свойств.
\end_layout

\begin_layout Section
Значения и типы
\end_layout

\begin_layout Definition
Элемент данных — это последовательность бит.
\end_layout

\begin_layout Standard
\begin_inset Separator plain
\end_inset


\end_layout

\begin_layout Definition
Значение — это элемент данных вместе с его интерпретацией.
\end_layout

\begin_layout Standard
\begin_inset Separator plain
\end_inset


\end_layout

\begin_layout Definition
Тип значений — это множество значений, имеющих общую интерпретацию.
\end_layout

\begin_layout Standard
\begin_inset Separator plain
\end_inset


\end_layout

\begin_layout Definition
Объект — это набор битов в памяти, содержащий значение определённого типа
 значений.
\end_layout

\begin_layout Standard
На самом деле нередко бывает, что части объекта находятся в разных областях
 памяти, тогда они называются 
\emph on
отдалёнными частями
\emph default
.
 Объект называется 
\emph on
неизменяемым
\emph default
, если его значение никогда не изменяется, и 
\emph on
изменяемым 
\emph default
в противном случае.
\end_layout

\begin_layout Standard
Объект называется 
\emph on
неограниченным
\emph default
, если он может содержать любое значение своего типа.
\end_layout

\begin_layout Definition
Объектный тип — это единообразный метод хранения значений заданного типа
 значений в конкретном объекте и их извлечения из объекта при условии, что
 известен его адрес.
\end_layout

\begin_layout Section
Концепции
\end_layout

\begin_layout Standard
\begin_inset Tabular
<lyxtabular version="3" rows="4" columns="4">
<features tabularvalignment="middle">
<column alignment="center" valignment="top">
<column alignment="center" valignment="top">
<column alignment="center" valignment="top">
<column alignment="center" valignment="top">
<row>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Естественные науки
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Математика
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Программирование
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Примеры из программирования
\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Род
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Теория
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Концепция
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Integral, Character
\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Вид
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Модель
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Тип или класс
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
uint8_t, char
\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Индивидум
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Элемент
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Экземпляр
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
01000001 (65, 'A')
\end_layout

\end_inset
</cell>
</row>
</lyxtabular>

\end_inset


\end_layout

\begin_layout Standard
Концепцию можно рассматривать как набор требований к типам или как предикат,
 который проверяет, удовлетворяют ли типы этим требованиям.
 Требования могут относится к:
\end_layout

\begin_layout Itemize
операциям, которые обязан предоставить тип;
\end_layout

\begin_layout Itemize
семантике этих операций;
\end_layout

\begin_layout Itemize
сложности в терминах времени и/или памяти.
\end_layout

\begin_layout Standard
Рассмотрим некоторые очень общие концепции.
 Первая — 
\series bold
Regular
\series default
, мы рассматривали её в главе 7
\begin_inset Note Note
status open

\begin_layout Plain Layout
Добавить ссылку
\end_layout

\end_inset

.
\end_layout

\begin_layout Standard
С концепцией 
\series bold
Regular 
\series default
тесно связана концепция 
\series bold
Semiregular
\series default
, отличающаяся тем, что равенство явно не определено.
 Этот необходимо в тех немногих ситуациях, когда реализовать предикат проверки
 на равенство очень трудно.
 Но даже в таких случаях предполагается, что равенство определено неявно,
 поэтому аксиомы, связанные с копированием и присваиванием, остаются выполненным
и.
\end_layout

\begin_layout Section
Итераторы
\end_layout

\begin_layout Standard
Чтобы быть итератором, тип должен поддерживать следующие операции:
\end_layout

\begin_layout Itemize
операции регулярного типа;
\end_layout

\begin_layout Itemize
переход к следующему;
\end_layout

\begin_layout Itemize
разыменование.
\end_layout

\begin_layout Standard
Итераторы удовлетворяют подмножеству требований, предъявляемых аксиомами
 Пеано: для любого числа определено следующее, но в случае итераторов мы
 можем достичь конца данных.
 У Пеано если равны следующие, то равны и предыдущие, а также запрещены
 циклы, тогда как для структур данных они могут быть полезны.
\end_layout

\begin_layout Standard
Операции разыменования и перехода к следующему тесно связаны:
\end_layout

\begin_layout Itemize
разыменование определено для итератора тогда и только тогда, когда определён
 следующий;
\end_layout

\begin_layout Itemize
если итератор не находится в конце диапазона, то разыменование разрешено.
\end_layout

\begin_layout Standard
К итераторам предъявляются требования проверки на равенство, так как иногда
 важно знать, что один итератор 
\begin_inset Quotes rld
\end_inset

догнал
\begin_inset Quotes rrd
\end_inset

 другой.
\end_layout

\begin_layout Section
Категории, операции и характеристики итераторов
\end_layout

\begin_layout Section
Диапазоны
\end_layout

\begin_layout Section
Линейный поиск
\end_layout

\begin_layout Section
Двоичный поиск
\end_layout

\begin_layout Lemma
(О двоичном поиске) Для любого отсортированного диапазона 
\begin_inset Formula $\left[i;j\right)$
\end_inset

 и значения 
\begin_inset Formula $a$
\end_inset

 (искомого элемента) существуют два итератора, нижняя граница 
\begin_inset Formula $b_{l}$
\end_inset

 и 
\begin_inset Formula $b_{u}$
\end_inset

 такие, что:
\end_layout

\begin_layout Lemma
\begin_inset Formula $\forall k\in\left[i;b_{l}\right):v_{k}<a;$
\end_inset


\end_layout

\begin_layout Lemma
\begin_inset Formula $\forall k\in\left[b_{l};b_{u}\right):v_{k}=a;$
\end_inset


\end_layout

\begin_layout Lemma
\begin_inset Formula $\forall k\in\left[b_{u};j\right):v_{k}>a,$
\end_inset

 где 
\begin_inset Formula $v_{k}$
\end_inset

 — значение в позиции 
\begin_inset Formula $k$
\end_inset

.
\end_layout

\begin_layout Proof
Если для всех 
\begin_inset Formula $k\in\left[i;j\right)$
\end_inset

 имеет место 
\begin_inset Formula $v_{k}<a$
\end_inset

, то можно положить 
\begin_inset Formula $b_{l}=b_{u}=j$
\end_inset

.
 Если для всех 
\begin_inset Formula $k\in\left[i;j\right)$
\end_inset

 имеет место 
\begin_inset Formula $v_{k}>a$
\end_inset

, то можно положить 
\begin_inset Formula $b_{l}=b_{u}=i$
\end_inset

.
 Исключим эти два случая из дальнейшего рассмотрения.
 Возьмём в качестве 
\begin_inset Formula $b_{l}$
\end_inset

 первый по порядку итератор 
\begin_inset Formula $k$
\end_inset

 такой, что не выполняется 
\begin_inset Formula $v_{k}<a$
\end_inset

.
 Так как диапазон отсортирован, то при 
\begin_inset Formula $k\in\left[b_{l};j\right)$
\end_inset

 неравенство 
\begin_inset Formula $v_{k}<a$
\end_inset

 также не будет выполняться.
 Возьмём в качестве 
\begin_inset Formula $b_{u}$
\end_inset

 первый итератор 
\begin_inset Formula $k\in\left[b_{l};j\right)$
\end_inset

 такой, что 
\begin_inset Formula $v_{k}>a$
\end_inset

.
 Снова в силу того, что диапазон отсортирован будет выполняться третье свойство.
 Остаётся доказать второе свойство.
\end_layout

\begin_layout Proof
Исходя из выбора 
\begin_inset Formula $b_{l}$
\end_inset

 и 
\begin_inset Formula $b_{k}$
\end_inset

, для любого 
\begin_inset Formula $k\in\left[b_{l};b_{u}\right)$
\end_inset

 не выполняются неравенства 
\begin_inset Formula $v_{k}<a$
\end_inset

 и 
\begin_inset Formula $v_{k}>a$
\end_inset

, таким образом, если в этом диапазоне вообще есть элементы, то 
\begin_inset Formula $v_{k}=a$
\end_inset

.
\end_layout

\begin_layout Chapter
Алгоритмы перестановки
\end_layout

\begin_layout Section
Перестановки и транспозиции
\end_layout

\begin_layout Definition

\series bold
Перестановкой
\series default
 называется отображение последовательности 
\begin_inset Formula $n$
\end_inset

 объектов в себя.
\end_layout

\begin_layout Standard
\begin_inset Separator plain
\end_inset


\end_layout

\begin_layout Definition
Множество всех перестановок 
\begin_inset Formula $n$
\end_inset

 элементов составляют группу, называют 
\series bold
симметричной группой
\series default
 
\begin_inset Formula $S_{n}$
\end_inset

.
\end_layout

\begin_layout Exercise
Докажите следующую теорему.
 (Теорема Кэли) Любая конечная группа является подгруппой симметричной группы.
\end_layout

\begin_layout Solution
Рассмотрим группу 
\begin_inset Formula $G$
\end_inset

 порядка 
\begin_inset Formula $n$
\end_inset

.
 Для каждого элемента 
\begin_inset Formula $g\in G$
\end_inset

 рассмотрим отображение 
\begin_inset Formula $\varphi_{g}\left(x\right)=g\circ x$
\end_inset

.
 В силу аксиом группы, каждое такое отображение переводит группу 
\begin_inset Formula $G$
\end_inset

 в себя, причём разные элементы переводятся в различные.
 Действительно, если 
\begin_inset Formula $\varphi_{g}\left(a\right)=\varphi_{g}\left(b\right)$
\end_inset

, то 
\begin_inset Formula $g\circ a=g\circ b$
\end_inset

 и, умножая это равенство слева на 
\begin_inset Formula $g^{-1}$
\end_inset

, получим 
\begin_inset Formula $a=b$
\end_inset

.
 Таким образом, 
\begin_inset Formula $\varphi_{g}$
\end_inset

 является перестановкой элементов группы 
\begin_inset Formula $G$
\end_inset

.
 Таким образом, 
\begin_inset Formula $G$
\end_inset

 соответствует подмножеству множества всех перестановок элементов этой группы.
 Обозначим этот подмножество 
\begin_inset Formula $\Phi$
\end_inset

.
 Остаётся доказать, что данное подмножество является подгруппой.
\end_layout

\begin_layout Solution
Во-первых, множество замкнуто относительно групповой операции: 
\begin_inset Formula 
\[
\left(\varphi_{a}\varphi_{b}\right)\left(x\right)=\varphi_{a}\left(\varphi_{b}\left(x\right)\right)=a\circ\left(b\circ x\right)=\left(a\circ b\right)\circ x=\varphi_{a\circ b}\left(x\right),
\]

\end_inset

но так как по аксиомам группы 
\begin_inset Formula $a\circ b\in G$
\end_inset

, то 
\begin_inset Formula $\varphi_{a}\varphi_{b}=\varphi_{a\circ b}$
\end_inset

 принадлежит 
\begin_inset Formula $\Phi$
\end_inset

.
 Ассоциативность выполняется для композиции 
\begin_inset Formula $\varphi_{g}$
\end_inset

 как и для композиции любых отображений.
 Так как 
\begin_inset Formula $e\circ x=x$
\end_inset

, то 
\begin_inset Formula $\varphi_{e}\left(x\right)=x=Id\left(x\right)$
\end_inset

 тождественная перестановка входит в 
\begin_inset Formula $\Phi$
\end_inset

.
 Наконец, для любого 
\begin_inset Formula $\varphi_{g}$
\end_inset

 в 
\begin_inset Formula $\Phi$
\end_inset

 существует обратный элемент: 
\begin_inset Formula $\varphi_{g^{-1}}$
\end_inset

.
 Действительно, 
\begin_inset Formula $\varphi_{g}\varphi_{g^{-1}}=\varphi_{g\circ g^{-1}}=\varphi_{e}=Id$
\end_inset

.
 Таким образом, 
\begin_inset Formula $\Phi$
\end_inset

 является подгруппой 
\begin_inset Formula $S_{n}$
\end_inset

, изоморфной 
\begin_inset Formula $G$
\end_inset

.
 
\end_layout

\begin_layout Exercise
Чему равен порядок 
\begin_inset Formula $S_{n}$
\end_inset

.
\end_layout

\begin_layout Solution
Для первого элемента при перестановке можно выбрать любую из 
\begin_inset Formula $n$
\end_inset

 позиций, для второго — 
\begin_inset Formula $n-1$
\end_inset

, для третьего — 
\begin_inset Formula $n-2$
\end_inset

 и так далее.
 Таким образом, порядок группы 
\begin_inset Formula $S_{n}$
\end_inset

 равен 
\begin_inset Formula $n!$
\end_inset

.
\backslash

\end_layout

\begin_layout Definition

\series bold
Транспозицией 
\series default

\begin_inset Formula $\left(i,j\right)$
\end_inset

 называется перестановка, которая меняет местами 
\begin_inset Formula $i$
\end_inset

-ый и 
\begin_inset Formula $j$
\end_inset

-ый элементы (
\begin_inset Formula $i\neq j$
\end_inset

), оставляя все остальные элементы на месте.
\end_layout

\begin_layout Lemma
(лемма о транспозиции).
 Любая перестановка является произведением транспозиций.
\end_layout

\begin_layout Proof
Для выполнения любой перестановки 
\begin_inset Formula $n$
\end_inset

 элементов требуется не более 
\begin_inset Formula $n-1$
\end_inset

 транспозиций.
 Транспозиции можно выбрать так, что каждая из них будет устанавливать на
 место как минимум один элемент.
 После того как 
\begin_inset Formula $n-1$
\end_inset

 элемент окажется на своём месте, последний элемент также окажется на нужном
 месте, так как остальные места уже будут заняты.
\end_layout

\begin_layout Exercise
Докажите, что при 
\begin_inset Formula $n>2$
\end_inset

 группа 
\begin_inset Formula $S_{n}$
\end_inset

 не является абелевой.
\end_layout

\begin_layout Solution
Достаточно предъявить две перестановки, произведение которых зависит от
 порядка умножения.
 Для 
\begin_inset Formula $n=3$
\end_inset

 можно взять 
\begin_inset Formula $\left(\begin{array}{ccc}
1 & 2 & 3\\
2 & 3 & 1
\end{array}\right)$
\end_inset

 и 
\begin_inset Formula $\left(\begin{array}{ccc}
1 & 2 & 3\\
3 & 2 & 1
\end{array}\right)$
\end_inset

.
 Тогда 
\begin_inset Formula 
\[
\left(\begin{array}{ccc}
1 & 2 & 3\\
2 & 3 & 1
\end{array}\right)\left(\begin{array}{ccc}
1 & 2 & 3\\
3 & 2 & 1
\end{array}\right)=\left(\begin{array}{ccc}
1 & 2 & 3\\
1 & 3 & 2
\end{array}\right),
\]

\end_inset

 но
\end_layout

\begin_layout Solution
\begin_inset Formula 
\[
\left(\begin{array}{ccc}
1 & 2 & 3\\
3 & 2 & 1
\end{array}\right)\left(\begin{array}{ccc}
1 & 2 & 3\\
2 & 3 & 1
\end{array}\right)=\left(\begin{array}{ccc}
1 & 2 & 3\\
2 & 1 & 3
\end{array}\right).
\]

\end_inset


\end_layout

\begin_layout Solution
В случае 
\begin_inset Formula $n>3$
\end_inset

 можно взять перестановки, аналогичные указанным: 
\begin_inset Formula $\left(\begin{array}{cccccc}
1 & 2 & 3 & 4 & \dots & n\\
2 & 3 & 1 & 4 & \dots & n
\end{array}\right)$
\end_inset

 и 
\begin_inset Formula $\left(\begin{array}{cccccc}
1 & 2 & 3 & 4 & \dots & n\\
3 & 2 & 1 & 4 & \dots & n
\end{array}\right)$
\end_inset

.
\end_layout

\begin_layout Standard
Если выполнить любую перестановку достаточное число раз, то любой заданный
 элемент вернётся в исходную позицию.
 В процессе таких последовательных перестановок мы получим 
\emph on
цикл
\emph default
.
 Циклы не пересекаются.
 Находясь в любой позиции, принадлежащей циклу, можно перейти в любую другую
 позицию того же цикла.
 Поэтому, если у двух циклов есть общий элемент, то они совпадают.
 Таким образом, любая перестановка распадается на произведение не пересекающихся
 циклов.
\end_layout

\begin_layout Definition
Цикл из одного элемента называется 
\emph on
тривиальным
\emph default
.
\end_layout

\begin_layout Exercise
Сколько нетривиальных циклов может содержать перестановка 
\begin_inset Formula $n$
\end_inset

 элементов?
\end_layout

\begin_layout Solution
Так как нетривиальный цикл включает не менее двух элементов, то количество
 нетривиальных циклов не может превышать 
\begin_inset Formula $\left\lfloor \frac{n}{2}\right\rfloor $
\end_inset

.
\end_layout

\begin_layout Standard
Такая перестановка называется 
\emph on
обращением
\emph default
.
\end_layout

\begin_layout Theorem
(о числе присваиваний).
 Для выполнения произвольной перестановки на месте необходимо 
\begin_inset Formula $n-u+v$
\end_inset

 операций присваивания, где 
\begin_inset Formula $n$
\end_inset

 — число элементов, 
\begin_inset Formula $u$
\end_inset

 — число тривиальных циклов, а 
\begin_inset Formula $v$
\end_inset

 — число нетривиальных циклов.
\end_layout

\begin_layout Proof
Так как циклы не пересекаются, то количество операций присваивания, необходимых
 выполнения произвольной перестановки, равно суммарному количеству операций
 присваивания, необходимых для выполнения всех циклов.
\end_layout

\begin_layout Proof
Тривиальные циклы вообще не требуют выполнения никаких действий: они состоят
 из одного элемента, который находится на своём месте.
 Нетривиальный цикл из 
\begin_inset Formula $m$
\end_inset

 элементов требует для своего выполнения 
\begin_inset Formula $m+1$
\end_inset

 присваивание, одно для сохранения последнего элемента и 
\begin_inset Formula $m$
\end_inset

 для последовательной установки элементов в целевое место.
\end_layout

\begin_layout Proof
Пусть перестановка состоит из 
\begin_inset Formula $v$
\end_inset

 нетривиальных циклов из 
\begin_inset Formula $m_{1},\dots,m_{v}$
\end_inset

 элементов.
 Тогда для выполнения перестановки требуется 
\begin_inset Formula 
\[
\sum_{j=1}^{v}\left(m_{j}+1\right)=\sum_{j=1}^{v}m_{j}+v,
\]

\end_inset

 сумма в правой части, то есть суммарная число элементов в нетривиальных
 циклах, равна 
\begin_inset Formula $n-u$
\end_inset

, так как каждый нетривиальный цикл включает один элемент.
\end_layout

\begin_layout Exercise
Спроектируйте алгоритм обращения на месте для однонаправленных итераторов.
 Это означает что алгоритм должен работать для односвязных списков без изменения
 связей.
\end_layout

\begin_layout Solution
Нужно воспользоваться методом 
\begin_inset Quotes rld
\end_inset

разделяй и властвуй
\begin_inset Quotes rrd
\end_inset

: рекурсивно обратить половины диапазона, а затем обменять их местами.
 Диапазоны длины один обращать не нужно.
\end_layout

\begin_layout Section
Обмен диапазонов
\end_layout

\begin_layout Exercise
Почему мы не предоставляем интерфейс pair<I0, I1> swap_ranges(I0 first0,
 I1 first1, N0 n0, N1 n1).
\end_layout

\begin_layout Solution
Такой алгоритм будет вынужден взять наименьшее из 
\begin_inset Formula $n0$
\end_inset

 и 
\begin_inset Formula $n1$
\end_inset

 и вызвать версию с одним размером.
\end_layout

\begin_layout Section
Циклическая перестановка
\end_layout

\begin_layout Definition
Перестановка 
\begin_inset Formula $n$
\end_inset

 элементов 
\begin_inset Formula $k$
\end_inset

 позиций, где 
\begin_inset Formula $k\ge0$
\end_inset

: 
\begin_inset Formula 
\[
\left(k\mod n,k+1\mod n,\dots,k+n-1\mod n\right)
\]

\end_inset

 называется 
\series bold
циклической перестановкой 
\series default

\begin_inset Formula $n$
\end_inset


\series bold
 на
\series default
 
\begin_inset Formula $k$
\end_inset

.
\end_layout

\begin_layout Exercise
Докажите, что вызов rotate(f, m, l) — то есть обмен (возможно) не равных
 по длине диапазонов 
\begin_inset Formula $\left[f;m\right)$
\end_inset

 и 
\begin_inset Formula $\left[m;l\right)$
\end_inset

 — выполняет циклическую перестановку distance(f, l) на distance(m, l).
\end_layout

\begin_layout Proof
При выполнении указанного вызова элементы с номерами 
\begin_inset Formula $\left[m-f,\dots,l-f\right)$
\end_inset

 перемещаются в позиции 
\begin_inset Formula $\left[0,\dots,m-l\right)$
\end_inset

 с сохранением порядка.
 Элементы с номерами 
\begin_inset Formula $\left[0,\dots,m-f\right)$
\end_inset

 переходят в позиции 
\begin_inset Formula $\left[m-f,\dots,l-f\right)$
\end_inset

.
 Каждое из этих преобразований можно так: в позицию 
\begin_inset Formula $j$
\end_inset

 устанавливается элемент из позиции 
\begin_inset Formula $j+k\mod n$
\end_inset

, что совпадает с определением циклической перестановки.
\end_layout

\begin_layout Exercise
Внимательно изучив код swap_ranges, вы заметите, что производятся ненужные
 сравнения итераторов.
 Перепишите алгоритм так, чтобы никаких лишних сравнений не было.
\end_layout

\begin_layout Solution
Похоже, речь идёт о применении swap_ranges в rotate.
 Так как m достигнет l раньше, чем f, то сравнение f с m можно опустить.
\end_layout

\begin_layout Section
Использование циклов
\end_layout

\begin_layout Exercise
Докажите, что если циклическая перестановка 
\begin_inset Formula $n$
\end_inset

 элементов имеет тривиальный цикл, то она содержит 
\begin_inset Formula $n$
\end_inset

 тривиальных циклов (иначе говоря, циклическая перестановка либо перемещает
 все элементы, либо ни один).
\end_layout

\begin_layout Solution
Пусть у циклической перестановки 
\begin_inset Formula $n$
\end_inset

 элементов 
\begin_inset Formula $k$
\end_inset

 есть тривиальный цикл, состоящий из элемента 
\begin_inset Formula $j$
\end_inset

.
 Тогда, по определению циклической перестановки, 
\begin_inset Formula $j+k=j\mod n$
\end_inset

 или 
\begin_inset Formula $k=0\mod n$
\end_inset

.
 Но в этом случае для любого 
\begin_inset Formula $i$
\end_inset

 имеет место равенство 
\begin_inset Formula $i+k=i+0=i\mod n$
\end_inset

, что и требовалось доказать.
\end_layout

\begin_layout Exercise
Продолжите трассировку примера вплоть до завершения функции rotate.
 Это не математическое упражнение.
\end_layout

\begin_layout Section
Обращение
\end_layout

\begin_layout Standard
Ещё один фундаментальный алгоритм — 
\emph on
обращение 
\emph default
— изменяет порядок последовательности элементов на противоположный.
\end_layout

\begin_layout Exercise
Сколько присваиваний выполняет алгоритм циклической перестановки тремя вращениям
и.
\end_layout

\begin_layout Solution
Обращение 
\begin_inset Formula $n$
\end_inset

 элементов требует 
\begin_inset Formula $3\left\lfloor \frac{n}{2}\right\rfloor $
\end_inset

, так как выше было показано
\begin_inset Note Note
status open

\begin_layout Plain Layout
добавить ссылку
\end_layout

\end_inset

, что обращение представляет собой произведение 
\begin_inset Formula $\left\lfloor \frac{n}{2}\right\rfloor $
\end_inset

 транспозиций, то есть циклов длины 
\begin_inset Formula $2$
\end_inset

, а для осуществления цикла длины 
\begin_inset Formula $2$
\end_inset

 нужно выполнить 
\begin_inset Formula $3$
\end_inset

 операции.
\end_layout

\begin_layout Solution
rotate(f,m,l) потребует выполнения 
\begin_inset Formula 
\[
3\left(\left\lfloor \frac{m-f}{2}\right\rfloor +\left\lfloor \frac{l-m}{2}\right\rfloor +\left\lfloor \frac{l-f}{2}\right\rfloor \right)\le3\left(l-f\right)=3n.
\]

\end_inset


\end_layout

\begin_layout Solution
Меньше операций может потребоваться, если некоторые из диапазонов имеют
 нечётную длину.
\begin_inset Note Note
status open

\begin_layout Plain Layout
Проверить это
\end_layout

\end_inset


\end_layout

\begin_layout Exercise
Не математическое упражнение.
\end_layout

\begin_layout Standard
\begin_inset Separator plain
\end_inset


\end_layout

\begin_layout Exercise
Не математическое упражнение.
\end_layout

\begin_layout Section
Пространственная сложность
\end_layout

\begin_layout Section
Алгоритмы, адаптирующиеся к объёму памяти
\end_layout

\begin_layout Chapter
Обобщения НОД
\end_layout

\begin_layout Section
Аппаратные ограничения и более эффективный алгоритм
\end_layout

\begin_layout Section
Обобщение алгоритма Штайна
\end_layout

\begin_layout Exercise
Не математическое упражнение.
\end_layout

\begin_layout Section
Теорема Безу
\end_layout

\begin_layout Theorem
(Теорема Безу).
 
\begin_inset Formula $\forall a,b\thinspace\exists x,y:xa+yb=\gcd\left(a,b\right)$
\end_inset

.
\end_layout

\begin_layout Definition

\series bold
Идеалом 
\series default

\begin_inset Formula $I$
\end_inset

 называется непустое подмножество кольца 
\begin_inset Formula $R$
\end_inset

 такое, что 
\end_layout

\begin_layout Definition
\begin_inset Formula 
\[
\forall x,y\in I:x+y\in I,
\]

\end_inset


\begin_inset Formula 
\[
\forall x\in I,\forall a\in R:ax\in I.
\]

\end_inset


\end_layout

\begin_layout Exercise
1) Докажите, что идеал 
\begin_inset Formula $I$
\end_inset

 замкнут относительно вычитания.
\end_layout

\begin_layout Exercise
2).
 Докажите, что идеал 
\begin_inset Formula $I$
\end_inset

 содержит 0.
\end_layout

\begin_layout Solution
Пусть 
\begin_inset Formula $I$
\end_inset

 — идеал кольца 
\begin_inset Formula $R$
\end_inset

.
 Пусть 
\begin_inset Formula $x,y\in I$
\end_inset

.
 Нужно доказать, что 
\begin_inset Formula $x-y=x+\left(-y\right)\in I$
\end_inset

.
 Докажем, что 
\begin_inset Formula $\left(-y\right)=\left(-1\right)y$
\end_inset

.
 Действительно, 
\begin_inset Formula $\left(-1\right)y+y=\left(-1\right)\cdot y+1\cdot y=\left(\left(-1\right)+1\right)y=0\cdot y=0$
\end_inset

.
 Аналогично доказывается, что 
\begin_inset Formula $y+\left(-1\right)y=0$
\end_inset

.
 Так как обратный элемент является единственным, то 
\begin_inset Formula $\left(-1\right)y=\left(-y\right)$
\end_inset

.
 Так как 
\begin_inset Formula $-1\in R$
\end_inset

, а 
\begin_inset Formula $y\in I$
\end_inset

, то 
\begin_inset Formula $\left(-1\right)y=\left(-y\right)\in I$
\end_inset

 по второму свойству идеала, а значит 
\begin_inset Formula $x+\left(-y\right)=x-y\in I$
\end_inset

 по первому свойству идеала.
\end_layout

\begin_layout Solution
2) По определению, идеал 
\begin_inset Formula $I$
\end_inset

 не пуст, значит существует его некоторый элемент 
\begin_inset Formula $x\in I$
\end_inset

.
 Тогда, по определению кольца 
\begin_inset Formula $0\in R$
\end_inset

, тогда, по второму свойству идеалов 
\begin_inset Formula $0\cdot x=0\in I$
\end_inset

.
 Также можно опереться на первый пункт упражнения и сказать, что 
\begin_inset Formula $-x\in I$
\end_inset

, а значит 
\begin_inset Formula $x+\left(-x\right)=0\in I$
\end_inset

 по первому свойству идеала.
\end_layout

\begin_layout Lemma
(Об идеале линейных комбинаций).
 Для любого кольца и любых двух его элементов 
\begin_inset Formula $a$
\end_inset

 и 
\begin_inset Formula $b$
\end_inset

 множество элементов вида 
\begin_inset Formula $\left\{ xa+yb\right\} $
\end_inset

 образуют идеал.
\end_layout

\begin_layout Proof
Во-первых, 
\begin_inset Formula $I=\left\{ xa+yb\right\} \subset R$
\end_inset

, так как кольцо замкнуто относительно сложения и умножения.
 Рассмотрим теперь два элемента этого множества: 
\begin_inset Formula $x_{1}a+y_{1}b$
\end_inset

 и 
\begin_inset Formula $x_{2}a+y_{2}b$
\end_inset

.
 Тогда по свойствам кольца: 
\begin_inset Formula 
\[
\left(x_{1}a+y_{1}b\right)+\left(x_{2}a+y_{2}b\right)=\left(x_{1}+x_{2}\right)a+\left(y_{1}+y_{2}\right)b\in I,
\]

\end_inset

первое свойство идеала доказано.
\end_layout

\begin_layout Proof
Пусть теперь 
\begin_inset Formula $z\in R$
\end_inset

, рассмотрим произведение 
\begin_inset Formula $z\left(xa+yb\right)$
\end_inset

, по свойствам кольца: 
\begin_inset Formula 
\[
z\left(xa+yb\right)=\left(zx\right)a+\left(zy\right)b\in I,
\]

\end_inset

 таким образом, множество вида 
\begin_inset Formula $\left\{ xa+yb\right\} $
\end_inset

 действительно удовлетворяет определению идеала.
\end_layout

\begin_layout Exercise
Докажите, что все элементы идеала линейных комбинаций делятся на любой общий
 делитель 
\begin_inset Formula $a$
\end_inset

 и 
\begin_inset Formula $b$
\end_inset

.
\end_layout

\begin_layout Solution
Пусть 
\begin_inset Formula $g$
\end_inset

 — общий делитель 
\begin_inset Formula $a$
\end_inset

 и 
\begin_inset Formula $b$
\end_inset

, тогда существуют такие 
\begin_inset Formula $m$
\end_inset

 и 
\begin_inset Formula $n$
\end_inset

, что 
\begin_inset Formula $a=mg$
\end_inset

 и 
\begin_inset Formula $b=ng$
\end_inset

.
 Тогда 
\begin_inset Formula 
\[
xa+yb=xmg+yng=\left(xm+yn\right)g,
\]

\end_inset

то есть 
\begin_inset Formula $xa+yb$
\end_inset

 делится на 
\begin_inset Formula $g$
\end_inset

, что и требовалось доказать.
\end_layout

\begin_layout Lemma
(Об иделалах в евклидовых кольцах).
 Любой идеал евклидова кольца замкнут относительно операций взятия остатка
 и евклидова НОД.
\end_layout

\begin_layout Proof
Пусть 
\begin_inset Formula $R$
\end_inset

 — евклидово кольцо, а 
\begin_inset Formula $I$
\end_inset

 — его идеал.
 Пусть также 
\begin_inset Formula $x,y\in I$
\end_inset

.
 Сначала покажем, что 
\begin_inset Formula $r=reminder(x,y)\in I$
\end_inset

.
 По определению евклидова кольца, 
\begin_inset Formula $x=qy+r,$
\end_inset

 где 
\begin_inset Formula $q=quotient(x,y)\in R$
\end_inset

.
 Из этого представления следует 
\begin_inset Formula $r=x-qy$
\end_inset

.
 Так как 
\begin_inset Formula $q\in R$
\end_inset

 и 
\begin_inset Formula $y\in I$
\end_inset

, а 
\begin_inset Formula $I$
\end_inset

 — идеал, то 
\begin_inset Formula $qy\in I$
\end_inset

.
 Выше было показано, что идеал замкнут относительно операции вычитания,
 поэтому 
\begin_inset Formula $r=x-qy\in I$
\end_inset

.
 
\end_layout

\begin_layout Proof
Остаётся доказать, что идеал евклидова кольца замкнут относительно НОД.
 Это следует из того, что НОД определяется как последовательное применение
 взятия остатка.
\end_layout

\begin_layout Definition
Идеал 
\begin_inset Formula $I$
\end_inset

 кольца 
\begin_inset Formula $R$
\end_inset

 называется 
\series bold
главным идеалом
\series default
, если существует такой элемент 
\begin_inset Formula $a\in R$
\end_inset

, называемый 
\series bold
порождающим элементом 
\series default

\begin_inset Formula $I$
\end_inset

, что 
\begin_inset Formula 
\[
x\in I\Leftrightarrow\exists y\in R:x=ay.
\]

\end_inset


\end_layout

\begin_layout Standard
Иначе говоря, главный идеал порождён одним элементом.
\end_layout

\begin_layout Exercise
Докажите, что любой элемент главного идеала делится на порождающий элемент.
\end_layout

\begin_layout Solution
Следует непосредственно из определения главного идеала и делимости.
\end_layout

\begin_layout Definition
Область целостности называется 
\series bold
областью главных идеалов (ОГИ)
\series default
, если любой идеал в ней — главный.
\end_layout

\begin_layout Theorem
Любое евклидово кольцо является областью главных идеалов.
\begin_inset Note Note
status open

\begin_layout Plain Layout
Подмножество, состоящее только из нуля, является идеалом? Если да, то для
 этого случая утверждение тоже выполняется.
\end_layout

\end_inset


\end_layout

\begin_layout Proof
Пусть 
\begin_inset Formula $I$
\end_inset

 — некоторый идеал евклидова кольца 
\begin_inset Formula $R$
\end_inset

, который не является главным идеалом.
 В этом идеале существует элемент с наименьшей положительной нормой, обозначим
 его 
\begin_inset Formula $m$
\end_inset

.
 Докажем, что он является порождающим элементом.
 Так как 
\begin_inset Formula $I$
\end_inset

 не является главным идеалом, то существует такой элемент 
\begin_inset Formula $x$
\end_inset

, не кратный 
\begin_inset Formula $m$
\end_inset

, то есть для 
\begin_inset Formula $r=reminder\left(x,m\right)$
\end_inset

 справедливы неравенства 
\begin_inset Formula $0<\left\Vert r\right\Vert <\left\Vert m\right\Vert $
\end_inset

.
 Так как идеал замкнут относительно операции взятия остатка, то 
\begin_inset Formula $r\in I$
\end_inset

, таким образом, в идеале 
\begin_inset Formula $I$
\end_inset

 существует элемент, меньший по норме, чем 
\begin_inset Formula $m$
\end_inset

.
 Полученное противоречие означает, что любой элемент 
\begin_inset Formula $I$
\end_inset

 кратен 
\begin_inset Formula $m$
\end_inset

, то есть 
\begin_inset Formula $m$
\end_inset

 — порождающий элемент, а 
\begin_inset Formula $I$
\end_inset

 — главный идеал.
\end_layout

\begin_layout Standard
Теперь мы можем доказать теорему Безу, но сначала сформулируем её в терминах
 идеалов.
\end_layout

\begin_layout Theorem*
(теорема Безу в другой формулировке).
 Идеал линейных комбинаций 
\begin_inset Formula $I=\left\{ xa+yb\right\} $
\end_inset

 евклидового кольца 
\begin_inset Formula $R$
\end_inset

 содержит 
\begin_inset Formula $\gcd\left(a,b\right)$
\end_inset

.
\end_layout

\begin_layout Proof
Так как 
\begin_inset Formula $a=1\cdot a+0\cdot b$
\end_inset

 и 
\begin_inset Formula $b=0\cdot a+1\cdot b$
\end_inset

, то 
\begin_inset Formula $a,b\in I$
\end_inset

.
\end_layout

\begin_layout Proof
Так как идеал замкнут относительно операции взятия наибольшего общего делителя,
 то 
\begin_inset Formula $\gcd\left(a,b\right)\in I$
\end_inset

, а значит существуют такие 
\begin_inset Formula $x$
\end_inset

 и 
\begin_inset Formula $y$
\end_inset

, что 
\begin_inset Formula $xa+yb=\gcd\left(a,b\right)$
\end_inset

.
\end_layout

\begin_layout Lemma
(Лемма об обратимости).
 
\begin_inset Formula 
\[
\forall a,b\in\mathbb{Z}:\gcd\left(a,n\right)=1\Rightarrow\exists x\in\mathbb{Z}_{n}:ax=1\mod n.
\]

\end_inset


\end_layout

\begin_layout Proof
По теореме Безу существуют такие 
\begin_inset Formula $x$
\end_inset

 и 
\begin_inset Formula $y$
\end_inset

, что 
\begin_inset Formula $za+yn=\gcd\left(a,b\right)=1$
\end_inset

.
 Положив 
\begin_inset Formula $x=z\mod n$
\end_inset

 получим, что 
\begin_inset Formula $z=x+qn$
\end_inset

 и 
\begin_inset Formula $xa+qn-yn=1$
\end_inset

 или 
\begin_inset Formula $xa=1+(y-q)n$
\end_inset

, то есть 
\begin_inset Formula $xa=1\mod n$
\end_inset

.
 
\end_layout

\begin_layout Exercise
С помощью теоремы Безу докажите, что если 
\begin_inset Formula $p$
\end_inset

 — простое число, то для любого 
\begin_inset Formula $0<a<p$
\end_inset

 существует число, обратное 
\begin_inset Formula $a$
\end_inset

 относительно умножения по модулю 
\begin_inset Formula $p$
\end_inset

.
\end_layout

\begin_layout Solution
Так как 
\begin_inset Formula $p$
\end_inset

 простое, а 
\begin_inset Formula $0<a<p$
\end_inset

, то 
\begin_inset Formula $\gcd\left(a,p\right)=1$
\end_inset

, откуда по лемме об обратимости следует, что существует такое 
\begin_inset Formula $x$
\end_inset

, что 
\begin_inset Formula $ax=1\mod p$
\end_inset

.
\end_layout

\begin_layout Section
Расширенный алгоритм Евклида
\end_layout

\begin_layout Exercise
Чему равны 
\begin_inset Formula $x$
\end_inset

 и 
\begin_inset Formula $y$
\end_inset

, если 
\begin_inset Formula $b=0$
\end_inset

?
\end_layout

\begin_layout Solution
Так как 
\begin_inset Formula $\gcd\left(a,0\right)=a$
\end_inset

, то 
\begin_inset Formula $xa+yb=xa$
\end_inset

 и равенство 
\begin_inset Formula $xa+yb=a$
\end_inset

 выполняется при 
\begin_inset Formula $x=1$
\end_inset

 и любом 
\begin_inset Formula $y$
\end_inset

.
\end_layout

\begin_layout Exercise
Разработайте вариант расширенного алгоритма НОД на основе алгоритма Штайна.
\end_layout

\begin_layout Standard
\begin_inset Note Note
status open

\begin_layout Plain Layout
Закончить книгу (точнее её математическую часть)
\end_layout

\end_inset


\end_layout

\end_body
\end_document