23.12.2015 Шеина Г.В. Теория и практика решения задач по алгебре, часть 1

Глава 2. Теория делимости

Отметим, что операция умножения выполнима для любых натуральных чисел,

а операцию деления можно выполнить не всегда. Число 6 можно разделить на 3

и получить частное 2, являющееся натуральным числом, и нельзя подобрать натуральное число так, чтобы 6 = 4, или, по-другому, число 6 нельзя разде-

лить (нацело) на число 4. Мы рассмотрим в этой главе вопросы, связанные с делением, когда

одно натуральное или целое число делится нацело на другое;

можно осуществить такое деление не нацело, а с так называемым остат-

ком. Деление нацело является при этом частным случаем деления с остатком (остаток просто равен нулю).

Отметим, что деление с остатком мы выполняем в повседневной жизни, когда выясняем, например, какое максимальное количество карандашей можно ку-

пить, имея 200 рублей, если карандаш стоит 15 рублей. Задачи подобного рода предлагаются и на итоговых экзаменах по математике.

Делимость натуральных чисел

Определение. Если для натуральных чисел и существует такое натуральное число , что = , то говорят, что число делится нацело на число или что

делит .

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

числа , а число называется частным от деления числа на число .

Говорят также, что на множестве натуральных чисел задано отношение дели-

мости.

Обозначения

Запись означает, что число делится на число .

21

Запись | означает, что делит или, по-другому, есть делитель .

Свойства делимости натуральных чисел

1.Любое натуральное число делится на единицу: 1.

2.Единица делится только на единицу: 1 = 1.

3.Если число меньше числа , то не делится на число .

4.Если 1 , …, , то (1 + + ) .

Действительно, 1 1 = 1, аналогично = , поэтому

1 + + = 1 + + = (1 + + ), то есть (1 + + ) .

5.Если числа и делятся на , то числа + , | − |, ∙ делятся на число .

6.Если одно из чисел суммы двух чисел делится на число , а другое не де-

лится на , то сумма не делится на число .

7.Отношение делимости

рефлексивно, т.е. любое натуральное число делится на себя же: .

Действительно, = ∙ 1;

транзитивно, т.е. если и , то . Действительно,

= 1; = 2. Тогда = 1 2, то есть ;

не является симметричным (отсутствует симметричность):

если , то необязательно . Например, 4 2 является верным утверждением, но утверждение 2 4 не является верным;

антисимметрично, т.е. если и , то = . Действительно,

= 1, = 2 = 1 2 1 2 = 1 1 = 1 = .

Тем самым свойство делимости является отношением нестрогого порядка,

то есть обладает свойствами рефлексивности, антисимметричности и тран-

зитивности.

22

Связанные определения

У каждого натурального числа, большего единицы, имеется, по крайней ме-

ре, два натуральных делителя: единица и само это число. При этом нату-

ральные числа, имеющие ровно два делителя, называются простыми, а чис-

ла, имеющие больше двух делителей, — составными. Единица имеет ровно один делитель и не является ни простым, ни составным.

У каждого натурального числа, большего 1, имеется хотя бы один простой делитель.

Примеры составных чисел

1.Число 2727 составное, поскольку 2727 = 2700 + 27 = 27 ∙ (100 + 1).

2.Число 9991 составное, поскольку

9991=10000 − 9 = 1002 − 32 = (100 − 3) ∙ (100 + 3).

3.Число 8 + 1 является составным для любого натурального числа . Дей-

ствительно,

8 + 1 = (2 )3 + 1 = (2 + 1)(22 − 2 + 1).

4.Проверьте, что если число – составное, то число 1 … 1 – также

составное.

Делимость целых чисел

Определение. Если для целых чисел и существует такое целое число , что

= , то говорят, что число делится нацело на число или что делит .

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

числа , а число называется частным от деления на . Обозначения такие же, как и для натуральных чисел, в частности, означает, что число де-

лится на число .

Свойства делимости целых чисел несколько отличаются от свойств делимости натуральных чисел.

23

Свойства делимости целых чисел

1.(Отличие от натуральных чисел.) Ноль делится на любое целое число и частное равно нулю: 0 .

2.(Отличие от натуральных чисел.) На ноль делится только ноль: 0= 0, причем частное в этом случае не определено.

3.Любое целое число делится на единицу: 1.

4.(Отличие от натуральных чисел.) Единица делится только на единицу

или единицу со знаком минус:

1 1 = ∙ |1|=| | ∙ | | | | = 1 = ±1.

5. (Отличие от натуральных чисел.)

Если меньшее по модулю целое число делится на большее по модулю целое число, то меньшее число есть 0.

Действительно, пусть и | |<| |, тогда = и | |=| | ∙ | |. Если

| | ≠ 0 , то меньшее натуральное число разделилось на большее натураль-

ное число, что невозможно по свойствам делимости натуральных чисел. По-

этому | | = 0 = 0.

6. Если 1 , …, , то (1 + + ) .

Действительно, 1 1 = 1, аналогично = , поэтому

1 + + = 1 + + = (1 + + ), то есть (1 + + ) .

7. Если числа и делятся на , то числа + , − , ∙ делятся на число .

Отношение делимости целых чисел

рефлексивно, т.е. любое натуральное число делится на себя же: .

Действительно, = ∙ 1;

транзитивно, т.е. если и , то . Действительно,

= 1; = 2. Тогда = 1 2, то есть ;

24

не является симметричным (отсутствует симметричность):

если , то необязательно . Например, 4 2 является верным утверждением, но утверждение 2 4 не является верным;

(отличие от натуральных чисел) нет антисимметричности, т.е.

и , не верно, что = .

Действительно, = 1, = 2 = 1 2 1 2 = 11 = ±1 = ±.

Деление натуральных чисел с остатком

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

Определение. Говорят, что натуральное число разделено с остатком на нату-

ральное число , если представлено в виде: = + , где каждое из чисел

, либо натуральное, либо равно 0 и при этом 0 ≤ < .

Замечание. Условие 0 ≤ < можно заменить условием 0 ≤ ≤ − 1 , по-

скольку и – натуральные числа.

При этом числа и называются неполным частным и остатком соответ-

ственно.

Пример. Деление числа 2 на число 3 с остатком выглядит так:

2 = 3 ∙ 0 + 2 . Остаток = 2 удовлетворяет требуемому неравенству

= = = =

0 ≤ < .

Теорема (о возможности и однозначности деления натуральных чисел с остатком). Всякое натуральное число можно разделить на натуральное число

≠ 0 с остатком. При этом числа и определяются однозначно.

Доказательство. Индукцией по числу докажем существование непол-

ного частного и остатка.

25

Для числа = 1 утверждение верно, поскольку если = 1, то

Предположим теперь, что число = можно разделить с остатком на число , то есть можно представить в виде = + , 0 ≤ < . Покажем,

что + 1 можно разделить с остатком на число . Действительно,+ 1 = + + 1. Если + 1 < , то + 1 = и все доказано. В противном

ность деления доказана.

Проверим единственность деления с остатком.

Пусть есть два представления:

1.= 1 + 1 и 0 ≤ 1 < .

2.= 2 + 2 и 0 ≤ 2 < .

Если 1 ≠ 2, то пусть 1обозначен больший из двух остатков, то есть 1 > 2.

Тогда 1 + 1 = 2 + 2 ∙ ( 2 − 1) = 1 − 2. Но число 1 − 2 есть нату-

ральное число, меньшее, чем , или 0. Меньшее натуральное число 1 − 2 не может делиться на большее натуральное число . Поэтому

1 − 2 = 0. Но тогда ∙ ( 2 − 1) = 0 . Поскольку ≠ 0, то 2 − 1 = 0 или

2 = 1. Единственность доказана.

Деление целых чисел с остатком

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

от нуля.

Определение. Говорят, что целое число разделено с остатком на целое ло ≠ 0, если представлено в виде: = + , где , и число удовле-

творяет неравенству: 0 ≤ < | | (0 ≤ ≤ | | − 1).

26

При этом числа и называются неполным частным и остатком соответ-

ственно.

Замечание. Если целое число разделилось на целое число нацело (то есть с остатком 0) и при этом | | < | |, то = 0.

Теорема (о делении целых чисел с остатком).

Всякое целое число можно разделить на целое число ≠ 0 с остатком. При этом числа и определены однозначно.

Доказательство. Для доказательства возможности деления с остатком рассмотрим различные случаи.

Случай 1. Число – натуральное. В этом случае разделим на натураль-

ное число | | с остатком и получим = | | + , где 0 ≤ < | |.

Поскольку | | равен или − , то искомое представление имеет вид

, если| | =

= 1 + , где 1 = {− , если| | = − .

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

= ∙ 0 + 0 .

=0 = =

Случай 3. Число – отрицательное целое, тогда − есть натуральное число и по случаю 1 можно разделить число − на целое число с остатком:

− = + , 0 ≤ < | |.

Значит, = ∙ (− ) − .

Если = 0, то искомое представление получено. Если > 0, то

0 < < | | − | | < − < 0, | | − | | < | | − < | | + 0

0 < | | − < | |, то есть число | | − можно считать остатком, и тогда имеем

= ∙ (− ) − = ∙ (− ) − | | + ( | | − ).

27

Поскольку | | = ∙ , то = ∙ (− − ) + (| | − ).

Искомое представление получено.

Единственность. Пусть есть два различных представления

1.= 1 + 1 и 0 ≤ 1 < | |.

2.= 2 + 2 и 0 ≤ 2 < | |.

Тогда 1 + 1 = 2 + 2 ∙ ( 2 − 1) = 1 − 2. Но число | 1 − 2| есть це-

лое число, меньшее чем | |. Поэтому, по замечанию, приведенному выше, оно может делиться на , как это требуется для равенства

∙ ( 2 − 1) = 1 − 2 только в случае, если 1 − 2 = 0. Но тогда

∙ ( 2 − 1) = 0 . Поскольку ≠ 0, то 2 − 1 = 0 или 2 = 1. Единственность

доказана.

Наибольший общий делитель натуральных чисел

Определения.

1.Натуральное число c называется общим делителем натуральных чисел

1, 2, … , , если является делителем каждого из этих чисел.

2.Общий делитель называется наибольшим общим делителем нату-

ральных чисел 1, 2, … , , если делится на любой общий делитель этих чисел.

Из определения не ясно, существует ли наибольший общий делитель (Н. О. Д.) и

является ли он единственным. Общих делителей может быть несколько, поэто-

му можно говорить о множестве общих делителей. Для множества всех общих делителей чисел и мы будем использовать обозначение: {О. Д. ( , )} – мно-

жество общих делителей чисел , , то есть

{О. Д. ( , )} = { | – общий делитель чисел и }.

В следующих случаях Н. О. Д. существует и легко вычисляется.

28

Примеры

Если , то наибольший общий делитель Н. О. Д. ( , ) существует и равен .

Если | , то наибольший общий делитель Н. О. Д. ( , ) существует и равен .

Наибольший общий делитель натуральных чисел определен однозначно.

Докажем это.

Утверждение. Наибольший общий делитель натуральных чисел и опреде-

лен однозначно.

Действительно, если и 1 — два наибольших общих делителя натуральных чисел, то они являются и общими делителями, поэтому делятся друг на друга.

Значит, справедливы равенства = 1 и 1 = 1 , причем , 1 . Пере-

множив эти равенства, будем иметь 1 = 1 1, поэтому 1 = 1= 1 = 1 = 1 = 1 , что и требовалось доказать.

Нашей ближайшей задачей будет научиться находить наибольший общий дели-

тель двух чисел и . Кроме того, мы будем записывать его в виде

(линейной) комбинации этих чисел.

Докажем сначала следующий вспомогательный факт (лемму).

Лемма. Если в результате деления натурального числа на натуральное число

с остатком получено = + , где 0 ≤ ≤ − 1, то

{О. Д. ( , )} = {О. Д. ( , )}.

Действительно, из равенства = + видно, что любой общий делитель чи-

сел и является общим делителем чисел и .

Наоборот, поскольку = − , то любой общий делитель чисел и являет-

ся общим делителем чисел и . Поэтому множество общих делителей чисел и совпадает с множеством общих делителей чисел и , то есть

{О. Д. ( , )} = {О. Д. ( , )}.

29

Следствие. Если = + , где 0 ≤ ≤ − 1 и существует Н. О. Д. ( , ), то существует Н. О. Д. ( , ) и Н. О. Д. ( , ) = Н. О. Д. ( , ).

Для нахождения Н. О. Д. ( , ) используют алгоритм Евклида.

Алгоритм Евклида

Из определения наибольшего общего делителя следует, что

Н. О. Д. ( , ) = Н. О. Д. ( , ). Поэтому можно считать, что > .

Алгоритм Евклида состоит из следующих шагов.

Разделим число на число с остатком: = 1 + 1.

Если 1 = 0, то Н. О. Д. ( , ) = .

Если же 1 ≠ 0, то разделим число на число 1 с остатком: = 1 2 + 2, где

0 ≤ 2 < 1.

Продолжая дальше подобным образом, разделим остаток 1 на остаток 2 (если2 ≠ 0) с остатком и получим новый остаток 3, 0 ≤ 3 < 2.

Поскольку величины остатков строго убывают, являясь натуральными числа-

ми, то в некоторый момент очередной остаток (впервые) обратится в 0. Пусть это остаток +1, то есть +1 = 0. Имеем последовательность равенств:

= 1 + 1,

= 1 2 + 2,1 = 2 3 + 3,

−2 = −1 + ,−1 = +1 + 0.

Докажем, что Н. О. Д. ( , ) существует и Н. О. Д. ( , ) = , где – последний ненулевой остаток в алгоритме Евклида.

Действительно, по лемме {О. Д. ( , )} = {О. Д. ( , 1)} = {О. Д. ( 1, 2)} = = = {О. Д. ( −1, )}. Но | −1, и поэтому Н. О. Д. ( −1, ) = (смотри пример нахождения Н.О.Д. для случая | , рассмотренный выше). Значит, по след-

30