ДЕЛИМОСТЬ ЧИСЕЛ. ДЕЛЕНИЕ С ОСТАТКОМ. НАИБОЛЬШИЙ ОБЩИЙ ДЕЛИТЕЛЬ.

Известно, что сумма, разность и произведение целых чисел является целым числом. Этот факт принято называть замкнутостью множества целых чисел по отношению к действиям сложения, вычитания и умножения. По отношению к действию деления множество целых чисел, очевидно, замкнутым не является. Например, результат деления числа на число целым не является. Однако в некоторых случаях результат деления целого числа на целое число также является целым. Введем следующее определение.

Определение 1.1. Пусть и – целые числа. Говорят, что число делится на число , если найдется такое целое число , что . При этом число называют делимым, число – делителем, а число – частным.

Факт делимости числа на число обозначают . Также говорят, что кратно .

Примеры. 1) 65 13, так как ;

2) 0 3, так как ;

3) 5, так как .

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

.

Если , то . Значит, в случае, когда делитель отличен от нуля, частное единственно.

Если , то, очевидно, , и равенство выполняется для любого значения .Таким образом, на делится только , а частное от такого деления неопределенно (может быть любым числом).

В дальнейшем, говоря о делении, всегда будем предполагать, что делитель отличен от 0.

Свойства делимости

1. Если , то (– ); (– ) ; (– ) (– ).

Доказательство. Пусть , это значит, что существует такое целое число , что . Тогда , причем число также является целым. Следовательно, по определению делимости (– ). Остальные утверждения доказываются аналогично.

2. Если и , то .

Доказательство. , где ; , где . Тогда . Число – целое, значит, .

Следствие. Из свойств 1 и 2 непосредственно следует, что если и , то .

3. Если и , то .

Доказательство. , где . Умножим обе части последнего равенства на , получим . Число – целое, значит, .

4. Если и не делится на , то не делится на .

Доказательство. Предположим, что данное утверждение неверно: . Это значит, что , где . Тогда . Но , где . Следовательно, . Поскольку , получим, что , что противоречит условию. Полученное противоречие доказывает, что сделанное нами предположение неверно.

5. Если и , то .

Доказательство. , где , причем . Тогда . Но , значит .

Следствие 1. Если , то либо , либо .

Доказательство. Если , то по свойству 5 справедливо неравенство . При этом – целое число, отличное от 0. Следовательно, , а это и значит, что либо , либо .

Следствие 2. Если и , то либо , либо .

Доказательство. Если и , то по свойству 5 справедливы неравенства и . Одновременное выполнение этих неравенств может быть только в случае, когда , что и означает, что либо , либо .

Отметим, что отношение делимости является бинарным отношением на множестве . Рассмотрим его свойства делимости как бинарного отношения.

1. Рефлексивность. Очевидно, что . Значит, отношение делимости рефлексивно.

2. Проверим, обладает ли отношение делимости каким-либо из свойств симметричности, антисимметричности или асимметричности. По следствию 2 к свойству 5, если и , то либо , либо . Следовательно, ни одним из перечисленных свойств данное бинарное отношение не обладает.

Заметим, что если рассмотреть отношение делимости на множестве натуральных чисел N, то окажется, что это отношение обладает свойством антисимметричности. Действительно, в этом случае следствие 2 к свойству 5 примет вид: если и , то (поскольку на множестве N равенство невыполнимо).

3. Транзитивность отношения делимости означает, что если и , то . Докажем, что отношение делимости транзитивно. Действительно,

, где ;

, где .

Следовательно, , при этом, очевидно, , а это и означает, что .

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

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

Определение 2.1. Пусть и – целые числа. Разделить число на число с остатком, значит найти такие целые числа и , что выполняются условия:

1)

2) .

При этом называется неполным частным, а – остатком от деления на .

Примеры. 1) Разделить 5 на 3 с остатком. В соответствии с определением представим число 5 в виде: 5=3 1+2. Здесь . Условие 2 из определения, очевидно, выполняется.

2) Разделить (–5) на 3 с остатком: (–5)=3 (–2)+1. Здесь ; .

3) Разделить 5 на (–3) с остатком: 5=(–3) (–1)+2. Здесь ; .

4) Разделить (–5) на (–3) с остатком: (–5)=(–3) 2+1. Здесь ; .

Теорема 2.1. Пусть и – целые числа, причем . Число всегда можно разделить на число с остатком, причем единственным образом.

Доказательство. Рассмотрим случай, когда ,

1) Пусть . Рассмотрим последовательность чисел: … Поскольку , начиная с некоторого члена этой последовательности, все члены будут отрицательными. Пусть последним из неотрицательных членов будет число . Положим . Тогда , где . Докажем, что . Запишем это неравенство в виде . Если бы это неравенство не выполнялось, то . Последние неравенство противоречит тому, что является последним неотрицательным числом в последовательности. Таким образом мы доказали, что число делится на с остатком.

2) Пусть . Рассмотрим последовательность чисел: … Поскольку , начиная с некоторого члена этой последовательности, все члены будут положительными. Пусть – первое неотрицательное число в этой последовательности. Положим . Тогда , где . Докажем, что . Запишем это неравенство в виде . Предположим, что неравенство не выполняется, тогда . Но – первое неотрицательное число в последовательности. Полученное противоречие доказывает, что сделанное нами предположение неверно. Положим , тогда .

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

Случай, когда , рассматривается аналогично.

3) Докажем, что при делении одного целого числа на другое неполное частное и остаток определяются единственным образом. Пусть .

Предположим, что и , где и . Тогда . Поскольку , из последнего равенства следует, что . По свойству 5 делимости чисел, если , то , что невозможно в силу условий и . Следовательно, , а, значит, и . Случай, когда , рассматривается аналогично.