Делимость
Делимость является реальной отправной точкой теории чисел, поскольку она превращает целые числа в систему со структурой: вы перестаете рассматривать числа как «количества» и начинаете видеть их как элементы, которые либо согласуются, либо не согласуются друг с другом. С помощью одной-единственной структуры, a\mid b, можно выразить как критерии упрощения и факторизации, так и суть некоторых процедур, например алгоритма Евклида, позволяющего за считанные секунды вычислять наибольшие общие делители даже для больших чисел. Кроме того, делимость является технической основой идей, которые вновь и вновь возникают в прикладной математике и информатике: сравнения, модульная арифметика, проверки, коды и (на более позднем этапе) криптография. Овладеть делимостью по существу означает научиться обнаруживать невидимые закономерности в целых числах и превращать их в процедуры, которые работают всегда.
Цели обучения
По завершении данного конспекта студент сможет:
- Понимать отношение делимости между целыми числами.
- Понимать определение делимости и ее свойства.
- Разрабатывать математические доказательства результатов и теорем, связанных с делимостью.
ОГЛАВЛЕНИЕ
Определение делимости
Основные свойства делимости
Предлагаемые упражнения
Определение делимости
Неформальная идея «a делит b» становится строгой, когда мы выражаем ее как отношение между целыми числами. Будем говорить, что целое число a делит целое число b, если b может быть записано как точный кратный числа a. Это определение является основой всего конспекта, поскольку оно превращает выражения типа «делится без остатка» в проверяемый критерий.
Определение. Пусть a,b\in\mathbb{Z} и a\neq 0. Говорят, что a делит b, и пишут a\mid b, тогда и только тогда, когда существует целое число k\in\mathbb{Z} такое, что b=ka. В противном случае пишут a\nmid b.
a\mid b := (\exists k \in \mathbb{Z})(b = ka )
В этом определении число k называется частным (или множителем), связанным с делимостью. Например, утверждение 6\mid 42 эквивалентно утверждению о существовании k\in\mathbb{Z} такого, что 42=6k; в данном случае достаточно взять k=7.
Важно учитывать
- Условие a\neq 0 является существенным. Действительно, если бы мы попытались допустить a=0, то условие делимости требовало бы существования k\in\mathbb{Z} такого, что b=0\cdot k. Но 0\cdot k=0 для любого k, так что единственной возможностью было бы b=0. В этом случае не существовало бы «определенного» k, задаваемого данным отношением, поскольку любое k\in\mathbb{Z} удовлетворяет равенству 0=0\cdot k. Иными словами, неформальное выражение k=b/a превращается в k=0/0, которое не определено. Чтобы избежать этой дегенерации (когда понятие частного теряет смысл), требуется выполнение условия a\neq 0. По этой причине отношение 0\mid b не считается допустимым.
- Напротив, a\mid 0 верно для любого a\in\mathbb{Z} при a\neq 0, поскольку достаточно взять k=0, и выполняется равенство 0=a\cdot 0.
Из этого определения следует эквивалентность, которую мы будем использовать неоднократно: утверждение a\mid b равносильно утверждению, что b принадлежит множеству целых кратных числа a, то есть b\in a\mathbb{Z}, где a\mathbb{Z}=\{ak:\,k\in\mathbb{Z}\}. Такая запись подчеркивает, что делимость не является «приемом», а представляет собой способ описания строго структурированных подмножеств внутри \mathbb{Z}.
Основные свойства делимости
- Рефлексивность: a\mid a.
Доказательство:\begin{array}{rll} (1)&\vdash a=ka \leftrightarrow k=1 &\text{; Мультипликативная единица в $\mathbb{Z}$}\\ (2)&\vdash(\exists k \in \mathbb{Z})(a=ka) &\text{; Интр. существования (1)}\\ (3) &\vdash a \mid a &\text{; Определение делимости (2)} \\ &\blacksquare & \end{array}
- Транзитивность: если a\mid b и b\mid c, то a\mid c.
Доказательство:
\begin{array}{rll} (1)& \{a\mid b , b\mid c\} \vdash (\exists k_1\in\mathbb{Z})(b=k_1a) &\text{; Определение делимости, предположение}\\ (2)& \{a\mid b , b\mid c\} \vdash (\exists k_2\in\mathbb{Z})(c=k_2b) &\text{; Определение делимости, предположение}\\ (3)& \{a\mid b , b\mid c\} \vdash (\exists k_1,k_2\in\mathbb{Z})(b=k_1a \wedge c=k_2b) &\text{; $\exists$-компактация (1,2)}\\ (4)& \{a\mid b , b\mid c\} \vdash (\exists k_1,k_2\in\mathbb{Z})(k_2b=k_1k_2a \wedge c=k_2b) &\text{; Из (3)}\\ (5)& \{a\mid b , b\mid c\} \vdash (\exists k_1,k_2\in\mathbb{Z})( c=k_1k_2a) &\text{; Из (4)}\\ &\text{Алгебра внутри квантификатора}& \\ (6)& \{a\mid b , b\mid c\} \vdash (\exists k\in\mathbb{Z})( c=ka) &\text{; Из (5)}\\ &\text{Замкнутость $\mathbb{Z}$ относительно умножения}& \\ (7)& \{a\mid b , b\mid c\} \vdash a\mid c &\text{; Определение делимости (6)}\\ (8)& \vdash (a\mid b \wedge b\mid c) \rightarrow a\mid c &\text{; $\wedge$-TD (7)}\\ &\blacksquare& \end{array}
- Совместимость со сложением и вычитанием: если a\mid b и a\mid c, то a\mid (b+c) и a\mid (b-c).
Доказательство:\begin{array}{rll} (1)&\{a\mid b, a\mid c\}\vdash (\exists k_1 \in \mathbb{Z})(b=k_1 a) &\text{; Определение делимости, предположение}\\ (2)&\{a\mid b, a\mid c\}\vdash (\exists k_2 \in \mathbb{Z})(c=k_2 a) &\text{; Определение делимости, предположение}\\ (3)&\{a\mid b, a\mid c\}\vdash (\exists k_1, k_2 \in \mathbb{Z})(b=k_1 a \wedge c=k_2 a) &\text{; $\exists$-компактация (1,2)}\\ (4)&\{a\mid b, a\mid c\}\vdash (\exists k_1, k_2 \in \mathbb{Z})(b+c= (k_1+k_2)a) &\text{; Из (3)}\\ &\text{Алгебра внутри квантификатора.}& \\ (5)&\{a\mid b, a\mid c\}\vdash (\exists k \in \mathbb{Z})(b+c= ka) &\text{; Из (4)}\\ &\text{Замкнутость $\mathbb{Z}$ относительно сложения.}& \\ (6)&\{a\mid b, a\mid c\}\vdash a\mid (b+c) &\text{; Определение делимости (5)}\\ (7)&\vdash (a\mid b \wedge a\mid c) \rightarrow a\mid (b+c) &\text{; $\wedge$-TD (6)}\\ (8)&\{a\mid b, a\mid c\}\vdash (\exists k_1, k_2 \in \mathbb{Z})(b-c= (k_1-k_2)a) &\text{; Из (3)}\\ &\text{Алгебра внутри квантификатора.}& \\ (9)&\{a\mid b, a\mid c\}\vdash (\exists \overline{k} \in \mathbb{Z})(b-c= \overline{k}a) &\text{; Из (8)}\\ &\text{Замкнутость $\mathbb{Z}$ относительно вычитания.}& \\ (10)&\{a\mid b, a\mid c\}\vdash a\mid (b-c) &\text{; Определение делимости (9)}\\ (11)&\vdash (a\mid b \wedge a\mid c) \rightarrow a\mid (b-c) &\text{; $\wedge$-TD (10)}\\ (12)&\vdash (a\mid b \wedge a\mid c) \rightarrow \left(a\mid (b+c) \wedge a\mid (b-c)\right) &\text{; $\wedge$-интр. в консеквенте (7,11) }\\ &\blacksquare& \end{array}
- Совместимость с произведениями: если a\mid b, то a\mid (bc) для любого c\in\mathbb{Z}.
Доказательство:\begin{array}{rll} (1)& \{a\mid b\}\vdash (\exists k\in\mathbb{Z})(b=ka) &\text{; Определение делимости, предположение}\\ (2)& \{a\mid b\}\vdash \left(\forall c \in \mathbb{Z}\right) (\exists k\in\mathbb{Z})(cb=cka) &\text{; Из (1), $\forall$-интр. (c произвольно)}\\ &\text{Алгебра в }\mathbb{Z}\text{ внутри квантификатора существования.}&\\ (3)& \{a\mid b\}\vdash \left(\forall c \in \mathbb{Z}\right) (\exists \overline{k}\in\mathbb{Z})(cb=\overline{k}a) &\text{; Из (2), замкнутость: }\overline{k}=ck\\ (4)& \{a\mid b\}\vdash \left(\forall c \in \mathbb{Z}\right) (a \mid cb) &\text{; Определение делимости (3)}\\ (5)& \vdash a\mid b \rightarrow \left(\forall c \in \mathbb{Z}\right) (a \mid cb) &\text{; TD (4)}\\ &\blacksquare& \end{array}
Теорема: оценка делителя
Если b\neq 0 и a\mid b, то |a|\le |b|.
Доказательство:
\begin{array}{rll} (1) &\{b\in \mathbb{Z}\setminus\{0\} , a\mid b\}\vdash b \neq 0 & \text{; Предположение} \\ (2) &\{b\in \mathbb{Z}\setminus\{0\} , a\mid b\}\vdash (\exists k \in \mathbb{Z}) (b=ka) & \text{; Определение делимости, предположение} \\ (3) &\{b\in \mathbb{Z}\setminus\{0\} , a\mid b\}\vdash (\exists k \in \mathbb{Z}) (|b|=|k||a|) & \text{; Свойства абсолютной величины, из (2)} \\ (4) &\{b\in \mathbb{Z}\setminus\{0\} , a\mid b\}\vdash (\exists k \in \mathbb{Z}) (k\neq 0 \wedge |b|=|k||a|) & \text{; Из (1,3)} \\ (5) &\{b\in \mathbb{Z}\setminus\{0\} , a\mid b\}\vdash (\exists k \in \mathbb{Z}) (1\le |k| \wedge |b|=|k||a|) & \text{; Из (4), если }k\neq 0\Rightarrow |k|\ge 1 \\ (6) &\{b\in \mathbb{Z}\setminus\{0\} , a\mid b\}\vdash |a|\le |b| & \text{; Из (5)} \\ &\blacksquare& \end{array}
Предлагаемые упражнения
- Покажите, что теорема «оценка делителя» не обязательно верна, если b=0.
- Рассмотрим множество A и отношение \rho на этом множестве. Если элементы x,y\in A таковы, что x связано с y посредством \rho, то это записывается как x\rho y. Отношение \rho называется частичным порядком на A, если:
a)(\forall x\in A) (x\rho x),
b) (\forall x,y\in A) ( (x\rho y \wedge y\rho x) \rightarrow x=y)
c) (\forall x,y,z\in A) ( (x\rho y \wedge y\rho z) \rightarrow x\rho z).Докажите, что отношение делимости является отношением частичного порядка на множестве целых чисел.
- Докажите по индукции, что если a\mid b_1, a\mid b_2, \cdots, a\mid b_n, то a\mid \sum_{i=1}^n b_i x_i для любого множества \{x_i\}_{i=1}^n \subset \mathbb{Z}. Кроме того, докажите, что если a\mid b_i при i\in \{1,2,3,\cdots, n\} и c может быть записано как линейная комбинация этих b_i, то a\mid c.
- Если a\neq 0, покажите, что множество \{x\;:\; d\mid a\} является конечным.
- Рассмотрим фиксированное n\in\mathbb{Z}^+ и положим
S=\{d\,:\,d\in\mathbb{Z}^+ \wedge d\mid n\}
Докажите:
- d\in S \leftrightarrow n/d\in S
- Если элементы S упорядочены по возрастанию: 1=d_1 \lt d_2 \lt \cdots \lt d_t =n, то соответствующие элементы n\mid d_i при i \in \{1,2,\cdots, t\} расположены в порядке убывания.
- Пусть a,b\in\mathbb{Z}^+ и ab=c. Докажите, что \min\{a,b\}\le \sqrt{c}.
- Целое число n называется четным, если 2\mid n, и нечетным, если 2\nmid n. Докажите, что сумма и разность:
- двух четных чисел является четным числом.
- двух нечетных чисел является четным числом.
- четного и нечетного числа является нечетным числом.
- Если n — нечетное число, отличное от \pm 1, докажите, что n не может делить два последовательных четных числа.
- Пусть a,b,n\in\mathbb{Z} таковы, что |a-b|\lt |n|. Докажите, что n не может делить ни a, ни b.
- Пусть a\in\mathbb{Z}. Докажите, что:
- (\forall n \in \mathbb{Z})(a\mid n) \leftrightarrow a=\pm 1
- (\forall n \in \mathbb{Z})(n\mid a) \leftrightarrow a=0
- Пусть a,b,c\in\mathbb{Z} и предположим, что c\neq 0. Покажите, что из ac\mid bc следует, что a\mid b.