Начала теории целых чисел

Делимость с остатком

Прежде чем излагать новый материал, необходимо договориться о терминологии. Понятие остатка от деления положительного целог числа $B_{}$ на положительное целое число $A_{}$ не вызывает затруднений. А как определить остаток от деления отрицательного числа на положительное, например, числа $(-5)_{}$ на число $3_{}$ ? Можно действовать по схеме

$5=1\cdot 3 + 2 \ \Rightarrow \ -5=-1\cdot 3 - 2 \ ,$

и за остаток от деления $(-5)_{}$ на $3_{}$ принять отрицательное число $(-2)$ . Можно действовать по схеме

$5=1\cdot 3 + 2 \ \Rightarrow \ -5=-2\cdot 3 +1 \ ,$

и за остаток от деления $(-5)_{}$ на $3_{}$ взять положительное число $1_{}$ . Так вот, мы условимся находить остаток по второй схеме — т.е. всегда считать егонеотрицательным числом.

Зачем нужен такой занудный формализм? См. ☞ последний пример ПУНКТА.

Теорема. Всякое целое $B_{}$ представляется единственным образом с помощью целого $A>0$ равенством вида

$B=Aq+r\, , \quad npu \ \{q,r\} \subset \mathbb Z \ \ u \quad 0\le r<A \ .$

Доказательство. Возьмем $q = \lfloor B/A \rfloor$ . Тогда по определению целой части числа будет выполнено

$q \le \frac{B}{A}< q+1 \ \Rightarrow \ Aq \le B < Aq + A \ \Rightarrow \ 0 \le B- Aq< A \ .$

Положим $r= B- Aq$ , тогда получившаяся пара $q_{}$ и $r_{}$ удовлетворяет условиям теоремы.

Для доказательства единственности представления допустим существование еще одного:

$B=A \tilde{q}+\tilde{r} \quad npu \quad \{\tilde{q},\, \tilde{r}\} \subset \mathbb Z \ , \ 0\le \tilde{r}<A \ \ u \ \ \tilde{r} \ne r \ .$

Предположив для определенности, что $\tilde{r}>r$ , вычтем это представление из предыдущего. Приходим к равенству $A \left(q-\tilde{q} \right)=\tilde{r}-r$ . Поскольку в нем все числа целые, и $\tilde{r}-r<A$ , то оно возможно лишь при $q-\tilde{q}=0$ , но тогда и $\tilde{r}-r=0$ . Пришли к противоречию с предположением о неединственности представления числа $B_{}$ . ♦

В представлении

$B=Aq+r\, , \quad npu \ \{q,r\} \subset \mathbb Z \ \ u \quad 0\le r<A$

число $q_{}$ называется частным, а $r_{}$ — остатком1) от деления $B_{}$ на $A_{}$ . Если $r=0_{}$ , то говорят, что число $B_{}$ делится нацело на $A_{}$ или что $B_{}$ кратно $A_{}$ , а число $A_{}$ называется делителем $B_{}$ . Тривиальными делителями числа $A\ne 0$ называют $1_{}$ и само число $A_{}$ .

Для обозначения факта делимости $B_{}$ на $A_{}$ используют обозначение $A | B$ (в смысле, что число $A_{}$ является делителем числа $B_{}$ ). Мне это обозначение кажется неудобным и больше нравится $B \vdots A$ . Я не буду, однако, пользоваться обоими этими вариантами — словами понятнее.