Страница 418 - гдз по алгебре 10 класс учебник Мерзляк, Номировский

9. Системы счисления и кодирование.

Рекомендуемая литература:

1) Аршинов М. Н., Садовский Л. Е. Коды и математика (рассказы о кодировании). — М. : Наука, Главная редакция физико-математической литературы, 1983. (Библиотечка «Квант»; вып. 30).

2) Гашков С. Б. Системы счисления и их применение. — 2-е изд., испр. и доп. — М. : МЦНМО, 2012. (Библиотека «Математическое просвещение»; вып. 29).

3) Мир математики : в 40 т. Т. 2 : Жуан Гомес. Математики, шпионы и хакеры. Кодирование и криптография / пер. с англ. — М.: Де Агостини, 2014.

4) Оре О. Приглашение в теорию чисел. — 2-е изд., стер. / пер. с англ. — М. : Едиториал УРСС, 2003.

5) Фомин С. В. Системы счисления. — 5-е изд. — М. : Наука. Гл. ред. физ.-мат. лит., 1987. (Популярные лекции по математике; вып. 40).

1) Аршинов М. Н., Садовский Л. Е. Коды и математика (рассказы о кодировании). — М. : Наука, Главная редакция физико-математической литературы, 1983. (Библиотечка «Квант»; вып. 30).

2) Гашков С. Б. Системы счисления и их применение. — 2-е изд., испр. и доп. — М. : МЦНМО, 2012. (Библиотека «Математическое просвещение»; вып. 29).

3) Мир математики : в 40 т. Т. 2 : Жуан Гомес. Математики, шпионы и хакеры. Кодирование и криптография / пер. с англ. — М.: Де Агостини, 2014.

4) Оре О. Приглашение в теорию чисел. — 2-е изд., стер. / пер. с англ. — М. : Едиториал УРСС, 2003.

5) Фомин С. В. Системы счисления. — 5-е изд. — М. : Наука. Гл. ред. физ.-мат. лит., 1987. (Популярные лекции по математике; вып. 40).

10. Теоремы о приближении действительных чисел рациональными.

Рекомендуемая литература:

1) Бухштаб А. А. Теория чисел : учебное пособие. — 4-е изд., стер. — СПб. [и др.] : Лань, 2015. табл. — (Классическая учебная литература по математике).

2) Клецын В. А. Рациональные приближения действительных чисел. Летняя школа «Современная математика», 20 июля 2014 г., г. Дубна

3) Нестеренко Ю. В. Теория чисел. — М. : Издательский центр «Академия», 2008.

Приближение действительных чисел рациональными — центральная тема теории диофантовых приближений. Основной вопрос заключается в том, насколько хорошо данное действительное число $ \alpha $ может быть приближено рациональными дробями $ p/q $. Качество приближения измеряется величиной $ |\alpha - p/q| $ в зависимости от величины знаменателя $ q $.

Теорема Дирихле о диофантовых приближениях

Это фундаментальный результат в теории диофантовых приближений. Теорема утверждает, что любое действительное число можно достаточно хорошо приблизить рациональным.

Формулировка: Для любого действительного числа $ \alpha $ и любого целого числа $ N \ge 1 $ существуют целые числа $ p $ и $ q $ такие, что $ 1 \le q \le N $ и выполняется неравенство:

$$ |q\alpha - p| < \frac{1}{N} $$

Разделив на $ q $, получим эквивалентную форму:

$$ \left|\alpha - \frac{p}{q}\right| < \frac{1}{qN} $$

Поскольку $ q \le N $, из этого неравенства следует более слабое, но часто используемое следствие.

Следствие: Для любого иррационального числа $ \alpha $ существует бесконечно много рациональных чисел $ p/q $ таких, что:

$$ \left|\alpha - \frac{p}{q}\right| < \frac{1}{q^2} $$

Доказательство теоремы (принцип ящиков Дирихле): Рассмотрим $ N+1 $ число: $ 0, \{\alpha\}, \{2\alpha\}, \dots, \{N\alpha\} $, где $ \{x\} = x - \lfloor x \rfloor $ — дробная часть числа $ x $. Все эти числа лежат в полуинтервале $ [0, 1) $. Разобьем этот интервал на $ N $ "ящиков" — подынтервалов вида $ [\frac{k}{N}, \frac{k+1}{N}) $ для $ k=0, 1, \dots, N-1 $. Поскольку чисел у нас $ N+1 $, а ящиков $ N $, по принципу Дирихле хотя бы два числа, скажем $ \{k_1\alpha\} $ и $ \{k_2\alpha\} $ (где $ 0 \le k_2 < k_1 \le N $), попадут в один и тот же ящик. Расстояние между ними будет меньше длины ящика:

$$ |\{k_1\alpha\} - \{k_2\alpha\}| < \frac{1}{N} $$

$$ |(k_1\alpha - \lfloor k_1\alpha \rfloor) - (k_2\alpha - \lfloor k_2\alpha \rfloor)| < \frac{1}{N} $$

$$ |(k_1-k_2)\alpha - (\lfloor k_1\alpha \rfloor - \lfloor k_2\alpha \rfloor)| < \frac{1}{N} $$

Обозначим $ q = k_1-k_2 $ и $ p = \lfloor k_1\alpha \rfloor - \lfloor k_2\alpha \rfloor $. Тогда $ p $ и $ q $ — целые числа, причем $ 1 \le q \le N $. Мы получаем требуемое неравенство $ |q\alpha - p| < \frac{1}{N} $.

Ответ: Теорема Дирихле гарантирует, что любое действительное число $ \alpha $ можно приблизить рациональным числом $ p/q $ с точностью лучшей, чем $ 1/q^2 $. В частности, для любого иррационального $ \alpha $ существует бесконечно много дробей $ p/q $, удовлетворяющих неравенству $ |\alpha - \frac{p}{q}| < \frac{1}{q^2} $.

Связь с непрерывными дробями

Теорема Дирихле доказывает существование хороших приближений, но не указывает способ их нахождения. Конструктивный метод построения таких приближений дает аппарат непрерывных (цепных) дробей.

Любое действительное число $ \alpha $ можно представить в виде непрерывной дроби $ \alpha = [a_0; a_1, a_2, \dots] $. Конечные отрезки этой дроби, называемые подходящими дробями $ \frac{p_n}{q_n} = [a_0; a_1, \dots, a_n] $, являются наилучшими рациональными приближениями числа $ \alpha $.

Теорема о наилучших приближениях: Подходящие дроби $ p_n/q_n $ к числу $ \alpha $ являются наилучшими его приближениями в том смысле, что любая другая дробь $ p/q $ с меньшим знаменателем ($ q < q_n $) приближает $ \alpha $ хуже: $ |\alpha - p/q| > |\alpha - p_n/q_n| $.

Для любой подходящей дроби выполняется неравенство:

$$ \left|\alpha - \frac{p_n}{q_n}\right| < \frac{1}{q_n q_{n+1}} < \frac{1}{q_n^2} $$

Таким образом, все подходящие дроби к иррациональному числу удовлетворяют следствию из теоремы Дирихле, и их бесконечно много.

Ответ: Наилучшие рациональные приближения действительного числа $ \alpha $ даются его подходящими дробями, полученными из разложения $ \alpha $ в непрерывную дробь. Каждая подходящая дробь $ p_n/q_n $ удовлетворяет неравенству $ |\alpha - \frac{p_n}{q_n}| < \frac{1}{q_n^2} $.

Теорема Гурвица

Теорема Гурвица усиливает следствие из теоремы Дирихле, улучшая константу в знаменателе.

Формулировка: Для любого иррационального числа $ \alpha $ существует бесконечно много рациональных чисел $ p/q $ таких, что:

$$ \left|\alpha - \frac{p}{q}\right| < \frac{1}{\sqrt{5}q^2} $$

Константа $ \sqrt{5} $ в этой теореме является наилучшей возможной. Это означает, что если заменить $ \sqrt{5} $ на любое число $ C > \sqrt{5} $, то найдется иррациональное число $ \alpha $ (например, золотое сечение $ \phi = \frac{1+\sqrt{5}}{2} $), для которого неравенство $ |\alpha - \frac{p}{q}| < \frac{1}{Cq^2} $ будет иметь лишь конечное число решений.

Ответ: Теорема Гурвица уточняет теорему Дирихле, утверждая, что для любого иррационального числа $ \alpha $ существует бесконечно много рациональных приближений $ p/q $, удовлетворяющих более сильному неравенству $ |\alpha - \frac{p}{q}| < \frac{1}{\sqrt{5}q^2} $. Константа $ \sqrt{5} $ является наилучшей возможной.

Теорема Лиувилля и трансцендентные числа

Эта теорема устанавливает предел качества приближения для специального класса чисел — алгебраических.

Формулировка: Если $ \alpha $ — иррациональное алгебраическое число степени $ d \ge 2 $ (т.е. корень многочлена с целыми коэффициентами степени $ d $), то существует константа $ c(\alpha) > 0 $ такая, что для любого рационального числа $ p/q $ ($ q>0 $) выполняется неравенство:

$$ \left|\alpha - \frac{p}{q}\right| > \frac{c(\alpha)}{q^d} $$

Теорема показывает, что алгебраические числа нельзя приблизить рациональными "слишком хорошо". Это свойство позволило впервые доказать существование трансцендентных чисел (чисел, не являющихся алгебраическими). Числа, которые можно приблизить лучше, чем позволяет теорема Лиувилля для любой степени $ d $, называются числами Лиувилля. Например, число $ L = \sum_{k=1}^{\infty} 10^{-k!} $ является числом Лиувилля и, следовательно, трансцендентно.

Ответ: Теорема Лиувилля устанавливает, что иррациональные алгебраические числа степени $ d $ не могут быть "слишком хорошо" приближены рациональными числами. Точность приближения $ |\alpha - p/q| $ ограничена снизу величиной порядка $ 1/q^d $. Это позволило впервые доказать существование трансцендентных чисел.

Теорема Туэ-Зигеля-Рота

Этот результат является значительным усилением теоремы Лиувилля и одним из глубочайших в теории диофантовых приближений (Клаус Рот получил за него Филдсовскую премию в 1958 году).

Формулировка: Если $ \alpha $ — иррациональное алгебраическое число, то для любого $ \epsilon > 0 $ неравенство

$$ \left|\alpha - \frac{p}{q}\right| < \frac{1}{q^{2+\epsilon}} $$

имеет лишь конечное число решений в рациональных числах $ p/q $.

Эта теорема показывает, что показатель степени в знаменателе для алгебраических чисел не может быть существенно больше 2. Сравнение с теоремой Дирихле ($ |\alpha - p/q| < 1/q^2 $ имеет бесконечно много решений) показывает, что результат Туэ-Зигеля-Рота является, в некотором смысле, наилучшим возможным.

Ответ: Теорема Туэ-Зигеля-Рота является мощным обобщением теоремы Лиувилля. Она утверждает, что для любого иррационального алгебраического числа $ \alpha $ и любого $ \epsilon > 0 $ существует лишь конечное число рациональных приближений $ p/q $, удовлетворяющих неравенству $ |\alpha - \frac{p}{q}| < \frac{1}{q^{2+\epsilon}} $. Этот результат показывает, что с точки зрения качества рационального приближения алгебраические числа ведут себя почти так же, как и "большинство" иррациональных чисел.

11. Китайская теорема об остатках.

Рекомендуемая литература:

1) Бухштаб А. А. Теория чисел : учебное пособие. — 4-е изд., стер. — СПб. [и др.] : Лань, 2015. (Классическая учебная литература по математике).

2) Коутинхо С. Введение в теорию чисел. Алгоритм RSA. — М. : Постмаркет, 2001.

3) Нестеренко Ю. В. Теория чисел. — М. : Издательский центр «Академия», 2008.

Китайская теорема об остатках (КТО) — это результат теории чисел, который дает условия, при которых система линейных сравнений имеет единственное решение. Она имеет важное применение в криптографии, теории кодирования и других областях математики и информатики.

Формулировка теоремы

Пусть даны попарно взаимно простые натуральные числа $n_1, n_2, \dots, n_k$, то есть $\text{НОД}(n_i, n_j) = 1$ для всех $i \ne j$. Тогда для любых целых чисел $a_1, a_2, \dots, a_k$ система сравнений:

$\begin{cases} x \equiv a_1 \pmod{n_1} \\ x \equiv a_2 \pmod{n_2} \\ \vdots \\ x \equiv a_k \pmod{n_k} \end{cases}$

имеет решение, и это решение единственно по модулю $N = n_1 \cdot n_2 \cdot \dots \cdot n_k$.

Ответ: Теорема утверждает, что если модули $n_i$ попарно взаимно просты, то система линейных сравнений всегда имеет решение, которое уникально с точностью до прибавления кратных числа $N = n_1 \cdot n_2 \cdot \dots \cdot n_k$.

Доказательство и конструктивный метод решения

Доказательство теоремы является конструктивным, то есть оно не только доказывает существование решения, но и предоставляет метод его нахождения.

1. Обозначим $N = n_1 \cdot n_2 \cdot \dots \cdot n_k$.

2. Для каждого $i = 1, 2, \dots, k$ введем число $N_i = \frac{N}{n_i} = n_1 \cdot \dots \cdot n_{i-1} \cdot n_{i+1} \cdot \dots \cdot n_k$.

3. Поскольку все $n_j$ попарно взаимно просты, то для любого $i$ числа $N_i$ и $n_i$ также взаимно просты, то есть $\text{НОД}(N_i, n_i) = 1$.

4. Из того, что $\text{НОД}(N_i, n_i) = 1$, следует, что для каждого $N_i$ существует обратный элемент по модулю $n_i$. Найдем такое целое число $y_i$, что $N_i y_i \equiv 1 \pmod{n_i}$. Это число $y_i$ можно найти с помощью расширенного алгоритма Евклида.

5. Теперь мы можем построить решение системы. Искомое число $x$ находится по формуле:
$x = a_1 N_1 y_1 + a_2 N_2 y_2 + \dots + a_k N_k y_k = \sum_{i=1}^k a_i N_i y_i$.

Проверим, что это действительно решение. Рассмотрим $x$ по модулю $n_j$ для произвольного $j \in \{1, \dots, k\}$:
$x \pmod{n_j} = \left(\sum_{i=1}^k a_i N_i y_i\right) \pmod{n_j}$.
Заметим, что для любого $i \ne j$, число $N_i$ содержит в своем произведении множитель $n_j$, поэтому $N_i \equiv 0 \pmod{n_j}$. Таким образом, все слагаемые в сумме, кроме одного, обращаются в ноль по модулю $n_j$:
$x \equiv a_j N_j y_j \pmod{n_j}$.
Но мы выбрали $y_j$ так, что $N_j y_j \equiv 1 \pmod{n_j}$. Следовательно:
$x \equiv a_j \cdot 1 \pmod{n_j}$, что и требовалось доказать.

Для доказательства единственности предположим, что есть два решения, $x$ и $x'$. Тогда $x \equiv a_i \pmod{n_i}$ и $x' \equiv a_i \pmod{n_i}$ для всех $i$. Это означает, что их разность $x - x'$ делится на каждое $n_i$. Поскольку все $n_i$ попарно взаимно просты, их произведение $N$ также делит $x - x'$. Таким образом, $x - x' \equiv 0 \pmod N$, или $x \equiv x' \pmod N$.

Ответ: Решение системы находится по формуле $x = \sum_{i=1}^k a_i N_i y_i \pmod N$, где $N = \prod n_i$, $N_i = N/n_i$, и $y_i$ является мультипликативным обратным для $N_i$ по модулю $n_i$.

Пример

Решим систему сравнений:
$\begin{cases} x \equiv 2 \pmod{3} \\ x \equiv 3 \pmod{5} \\ x \equiv 2 \pmod{7} \end{cases}$

1. Модули $n_1=3, n_2=5, n_3=7$ попарно взаимно просты.
$N = 3 \cdot 5 \cdot 7 = 105$.

2. Находим $N_i$:
$N_1 = N/n_1 = 105/3 = 35$.
$N_2 = N/n_2 = 105/5 = 21$.
$N_3 = N/n_3 = 105/7 = 15$.

3. Находим обратные элементы $y_i$:
$N_1 y_1 \equiv 1 \pmod{n_1} \implies 35 y_1 \equiv 1 \pmod{3} \implies 2 y_1 \equiv 1 \pmod{3}$. Умножая на 2, получаем $4y_1 \equiv 2 \pmod{3} \implies y_1 \equiv 2 \pmod{3}$. Итак, $y_1=2$.
$N_2 y_2 \equiv 1 \pmod{n_2} \implies 21 y_2 \equiv 1 \pmod{5} \implies 1 y_2 \equiv 1 \pmod{5}$. Итак, $y_2=1$.
$N_3 y_3 \equiv 1 \pmod{n_3} \implies 15 y_3 \equiv 1 \pmod{7} \implies 1 y_3 \equiv 1 \pmod{7}$. Итак, $y_3=1$.

4. Вычисляем решение $x$:
$x_0 = a_1 N_1 y_1 + a_2 N_2 y_2 + a_3 N_3 y_3$
$x_0 = 2 \cdot 35 \cdot 2 + 3 \cdot 21 \cdot 1 + 2 \cdot 15 \cdot 1 = 140 + 63 + 30 = 233$.

5. Находим наименьшее неотрицательное решение:
$x = 233 \pmod{105} = 23$.

Проверка:
$23 = 7 \cdot 3 + 2 \implies 23 \equiv 2 \pmod{3}$.
$23 = 4 \cdot 5 + 3 \implies 23 \equiv 3 \pmod{5}$.
$23 = 3 \cdot 7 + 2 \implies 23 \equiv 2 \pmod{7}$.

Ответ: $x \equiv 23 \pmod{105}$.