Предварительные сведения

Для $n = 5, 8, 12, 20$ и $25$ найдите все положительные целые числа, меньшие $n$ и взаимно простые с $n$.

Вычислите

Вычислите $51 \bmod 13$, $342 \bmod 85$, $62 \bmod 15$, $10 \bmod 15$, $(82 \cdot 73) \bmod 7$, $(51+68) \bmod 7$, $(35 \cdot 24) \bmod 11$ и $(47+68) \bmod 11$.

Найдите целые числа $s$ и $t$, для которых $1 = 7 \cdot s + 11 \cdot t$. Покажите, что $s$ и $t$ определяются неоднозначно.

Докажите, что любое целое число, являющееся общим кратным всех элементов конечного множества целых чисел, кратно наименьшему общему кратному этих чисел.

Докажите, что среди любых трёх последовательных целых чисел $n$, $n + 1$, $n + 2$ найдётся число, делящееся на $3$.

Покажите, что для положительных целых чисел $a$ и $b$ выполняется $ab = \operatorname {lcm}(a, b) \cdot \gcd (a, b)$.

Пусть целые числа $a$ и $b$ делят целое число $c$. Покажите, что если $a$ и $b$ взаимно просты, то $ab$ делит $c$. Приведите пример, показывающий, что без условия взаимной простоты $a$ и $b$ число $ab$ не обязательно делит $c$.

Пусть $a$ и $b$ — целые числа, а $n$ — положительное целое число. Докажите, что $a \bmod n = b \bmod n$ тогда и только тогда, когда $n$ делит $a - b$.

Пусть $d = \gcd (a, b)$. Покажите, что если $a = da'$ и $b = db'$, то $\gcd (a', b') = 1$.

Пусть $n$ — фиксированное целое число, большее $1$. Если $a \bmod n = a'$ и $b \bmod n = b'$, докажите, что $(a+b) \bmod n = (a'+b') \bmod n$ и $(ab) \bmod n = (a'b') \bmod n$. (На это упражнение имеются ссылки в главах 6, 8, 10 и 15.)

Пусть $a$ и $b$ — положительные целые числа, $d = \gcd (a, b)$ и $m = \operatorname {lcm}(a, b)$. Если $t$ делит и $a$, и $b$, докажите, что $t$ делит $d$. Если $s$ кратно и $a$, и $b$, докажите, что $s$ кратно $m$.

Пусть $n$ и $a$ — положительные целые числа и $d = \gcd (a, n)$. Покажите, что уравнение $ax \bmod n = 1$ имеет решение тогда и только тогда, когда $d = 1$. (На это упражнение имеется ссылка в главе 2.)

Теорема 0.2 (представление НОД в виде линейной комбинации) утверждает: для любых ненулевых целых чисел $a$ и $b$ существуют целые числа $s$ и $t$, для которых $\gcd (a, b) = as + bt$; более того, $\gcd (a, b)$ — наименьшее положительное целое число вида $as + bt$. Следствие из этой теоремы утверждает: целые числа $a$ и $b$ взаимно просты тогда и только тогда, когда существуют целые числа $s$ и $t$, для которых $as + bt = 1$.

Покажите, что $5n + 3$ и $7n + 4$ взаимно просты при всех $n$.

Пусть $m$ и $n$ взаимно просты, а $r$ — любое целое число. Покажите, что существуют целые числа $x$ и $y$, для которых $mx + ny = r$.

Пусть $p$, $q$ и $r$ — простые числа, отличные от $3$. Покажите, что $3$ делит $p^2 + q^2 + r^2$.

Докажите, что любое простое число, большее $3$, можно записать в виде $6n + 1$ или $6n + 5$.

Вычислите $7^{1000} \bmod 6$ и $6^{1001} \bmod 7$.

Пусть $a$, $b$, $s$ и $t$ — целые числа. Покажите, что из $a \bmod st = b \bmod st$ следуют $a \bmod s = b \bmod s$ и $a \bmod t = b \bmod t$. Какое условие на $s$ и $t$ необходимо, чтобы обратное утверждение было верным? (На это упражнение имеется ссылка в главе 8.)

Пусть $n$ — целое число, большее $1$, и $(n - 1)! \equiv 1 \pmod n$. Докажите, что $n$ — простое число.

Покажите, что $\gcd (a, bc) = 1$ тогда и только тогда, когда $\gcd (a, b) = 1$ и $\gcd (a, c) = 1$. (На это упражнение имеется ссылка в главе 8.)

Пусть $p_1, p_2, \ldots , p_n$ — простые числа. Покажите, что $p_1 p_2 \cdots p_n + 1$ не делится ни на одно из них.

Докажите, что простых чисел бесконечно много.

Докажите, что для любых комплексных чисел $z_1$ и $z_2$ выполняется $\left|z_1 z_2\right| = \left|z_1\right|\left|z_2\right|$.

Сформулируйте с помощью слов «тогда и только тогда» условие, при котором логический элемент $x$ NAND $y$, описываемый формулой $1 + xy$, выдаёт $1$. Сформулируйте с помощью слов «тогда и только тогда» условие, при котором логический элемент $x$ XNOR $y$, описываемый формулой $1 + x + y$, выдаёт $1$.

Для входных значений $0$ и $1$ и арифметики по модулю $2$ опишите результат вычисления формулы $z + xy + xz$ в виде «Если $x \ldots$, то , иначе $\ldots$».

Докажите, что для любого положительного целого $n$ множество из ровно $n$ элементов имеет ровно $2^n$ подмножеств (включая пустое множество и всё множество).

Докажите, что $2^n 3^{2n} - 1$ всегда делится на $17$.

Докажите, что существует положительное целое число $n$, для которого все числа $n, n + 1, n + 2, \ldots , n + 200$ составные.

Пусть $p$ — простое число, делящее $a_1 a_2 \ldots a_n$. Докажите, что $p$ делит $a_i$ при некотором $i$.

С помощью обобщённой леммы Евклида (см. упражнение 0.30) докажите утверждение о единственности в основной теореме арифметики.

Основная теорема арифметики (теорема 0.3) утверждает: любое целое число, большее $1$, является простым или произведением простых чисел, причём это произведение единственно с точностью до порядка множителей. Иными словами, если $n = p_1 p_2 \cdots p_r$ и $n = q_1 q_2 \cdots q_s$, где числа $p$ и $q$ простые, то $r = s$ и после перенумерации чисел $q$ выполняется $p_i = q_i$ для всех $i$.

Какова наибольшая ставка, которую нельзя сделать с помощью фишек стоимостью $7.00 и $9.00? Проверьте свой ответ с помощью обеих форм математической индукции.

Докажите, что первый принцип математической индукции является следствием принципа наименьшего элемента.

Числа Фибоначчи образуют последовательность $1, 1, 2, 3, 5, 8, 13, 21, 34, \ldots$. В общем случае они определяются равенствами $f_1 = 1$, $f_2 = 1$ и $f_n = f_{n-1} + f_{n-2}$ при $n \geq 3$. Докажите, что $n$-е число Фибоначчи $f_n$ удовлетворяет неравенству $f_n < 2^n$.

Докажите индукцией по $n$, что для любого положительного целого $n$ число $n^3 + (n + 1)^3 + (n + 2)^3$ кратно $9$.

Пусть дано утверждение, зависящее от положительного целого параметра $n$, и доказано, что из его справедливости при некотором $n$ следует его справедливость при $n + 2$. Что ещё нужно сделать, чтобы доказать утверждение для всех положительных целых чисел? Опишите ситуацию, в которой применим такой способ доказательства.

В песне «As» из альбома Songs in the Key of Life Стиви Уандер упоминает равенство $8 \times 8 \times 8 = 4$. Найдите все целые числа $n$, для которых это равенство верно по модулю $n$.

Докажите, что для любого целого $n$ выполняется $n^3 \bmod 6 = n \bmod 6$.

Если сейчас 2:00 ночи, сколько времени будет через 3736 часов?

Найдите контрольную цифру денежного перевода с идентификационным номером $7234541780$.

Предположим, что в одном из разрядов номера денежного перевода, кроме контрольного, цифру $9$ заменили на $0$ или наоборот. Докажите, что контрольная цифра не обнаружит эту ошибку. Докажите, что все остальные ошибки в одном разряде обнаруживаются.

Предположим, что идентификационный номер денежного перевода вместе с контрольной цифрой $21720421168$ ошибочно переписали как $27750421168$. Обнаружит ли контрольная цифра эту ошибку?

Ошибка перестановки различных соседних цифр имеет вид $\ldots ab \ldots \to \ldots ba \ldots$, где $a \neq b$. Докажите, что схема контрольной цифры денежного перевода не обнаруживает такие ошибки, если в перестановке не участвует сама контрольная цифра.

Объясните, почему контрольная цифра денежного перевода с номером $N$ совпадает с повторяющейся цифрой в десятичной записи действительного числа $N \div 9$.

Десятизначный международный стандартный книжный номер (ISBN-10) $a_1a_2a_3a_4a_5a_6a_7a_8a_9a_{10}$ обладает свойством $(a_1, a_2, \ldots , a_{10}) \cdot (10, 9, 8, 7, 6, 5, 4, 3, 2, 1) \bmod 11 = 0$. Цифра $a_{10}$ является контрольной. Если для обращения скалярного произведения в $0$ требуется значение $a_{10} = 10$, в качестве контрольной цифры используют символ X. Проверьте контрольную цифру ISBN-10, присвоенного этой книге.

Предположим, что в ISBN-10 стёрлась цифра, на месте которой в записи $0\text{-}716?\text{-}2841\text{-}9$ стоит вопросительный знак. Найдите пропущенную цифру.

Предположим, что три последовательные цифры $abc$ номера ISBN-10 переставлены в порядке $bca$. Какие ошибки такого вида останутся незамеченными?

Пусть $S$ — множество действительных чисел. Для $a, b \in S$ положим $a \sim b$, если $a - b$ — целое число. Покажите, что $\sim$ является отношением эквивалентности на $S$. Опишите классы эквивалентности множества $S$.

Пусть $S$ — множество целых чисел. Для $a, b \in S$ положим $aRb$, если $ab \geq 0$. Является ли $R$ отношением эквивалентности на $S$?

Пусть $S$ — множество целых чисел. Для $a, b \in S$ положим $aRb$, если $a + b$ чётно. Докажите, что $R$ — отношение эквивалентности, и найдите классы эквивалентности множества $S$.

Завершите доказательство теоремы 0.7, показав, что $\sim$ является отношением эквивалентности на $S$.

Теорема 0.7 (разбиение на классы эквивалентности) утверждает: классы эквивалентности отношения эквивалентности на множестве $S$ образуют разбиение $S$; обратно, для любого разбиения $P$ множества $S$ существует отношение эквивалентности на $S$, классами которого являются элементы $P$. Доказательство обратного утверждения начинается так: пусть $P$ — семейство непустых попарно непересекающихся подмножеств $S$, объединение которых равно $S$; положим $a \sim b$, если $a$ и $b$ принадлежат одному и тому же подмножеству этого семейства. Остаётся показать, что $\sim$ — отношение эквивалентности на $S$.

Докажите, что $3$, $5$ и $7$ — единственная тройка последовательных нечётных целых чисел, каждое из которых простое.