Введение
Делимость - фундаментальное
понятие алгебры и теории чисел. Особенно
важную роль делимость играет в числовых
кольцах. Числовым кольцом называется
множество комплексных чисел, содержащее
единицу 1 и замкнутое относительно арифметических
операций сложения, вычитания и умножения.
Если числовое кольцо является полем,
т. е. каждый его элемент делится на каждый
ненулевой элемент, то в нем теория делимости
тривиальна.
Числовые кольца редко бывают
факториальными (гауссовыми), т. е. кольцами,
в которых выполняется основная теорема
арифметики [1, 4, 8, 11-13]. По идее немецкого
математика Э. Куммера, в ряде случаев
единственность разложения на неприводимые
множители удается восстановить за счет
добавления идеальных чисел (дивизоров);
для таких колец существует теория дивизоров.
К ним относятся дедекиндовы кольца, названные
так по имени другого немецкого математика
Р. Дедекинда, определившего понятие идеала
кольца и развившего теорию дивизоров
числовых колец на основе теории идеалов
(вторая половина XIX века). В качестве идеальных
чисел у Дедекинда выступали неглавные
идеалы кольца. В первой половине XIX века
в трудах К. Гаусса была создана теория
сравнений, развивающая и обогащающая
понятие делимости [1, 8, 11, 13].
Отношение делимости в кольцах
определяется мультипликативно, через
одну операцию умножения. Однако многие
свойства делимости в кольцах выражаются
с привлечением и операции сложения и
возможности сравнивать элементы кольца
по величине (абсолютная величина целого
числа, степень многочлена, норма комплексного
числа).
В самом общем и чистом виде
делимость можно изучать в группоидах.
Наиболее приспособленными для этого
являются целые полугруппы [3, 7, 9]
Глава I.
О делимости целых чисел.
Из всех действий арифметики
самое своенравное — это деление.
Оно
обладает особыми свойствами, можно сказать,
особым «нравом». Возьмем хотя бы обращение
с нулем. Для всех других арифметических
действий нуль — равноправное число. Его
можно и прибавлять и вычитать; оно может
быть множителем в действии умножения,
но делителем никогда. Разделить на нуль
вообще нельзя никакое число, никакое
алгебраическое выражение. Это — важная
особенность деления, и если к ней отнестись
невнимательно, то легко попасть впросак;
можно, скажем, «доказать» любое заведомо
фальшивое утверждение — «парадокс».
Как вы отнесетесь,
например, к такому утверждению.
Всякое количество
равно своей, половине.
«Доказательство».
Пусть a и b — два равных количества: a =
b. Умножим обе части этого равенства на
a:
a2 =
ab.
Теперь уменьшим на
b2 и
левую и правую части равенства. Получившиеся
разности а2 -
b2 и
ab - b2тоже
будут равными:
а2 -
b2 =
ab - b2.
Разложим на множители:
(а + b) (а – b) = b(а
– b).
Делим обе части равенства
на а – b, после чего получается такое равенство:
а + b = b.
Так как b = а, то в последнем
равенстве можем заменить b через a, тогда
a + a = a, или 2a = a. Разделив на 2, получим a
= a/2, а это значит, что целое равно своей
половине (?).
Внешне, или, как говорят,
«формально» все правильно, а по существу
где-то в приведенных выкладках есть дефект.
Вы, конечно, были внимательны и заметили,
в какой части преобразований имеется
изъян.
«Нрав» деления проявляется
не только по отношению к нулю. Математическая
теория уделяет много внимания свойствам
целых чисел и законам, управляющим действиями
над ними. Так вот, если ограничиться множеством
одних только целых (положительных и отрицательных)
чисел, то опять-таки «капризничает» только
одно действие: деление. Оно, как вы знаете,
не всегда выполнимо в области целых чисел.
Принято считать так, что целое число a делится на целое число b,
если среди целых же чисел найдется такое
число c, произведение которого на b дает
точно числоa; если же такого числа нет,
то a не делится на b.
Все эти особенности
деления и способствовали возникновению
таких понятий, как простые числа, наибольший
общий делитель (Н. О. Д.), наименьшее общее
кратное (Н. О. К.), признаки делимости чисел,
а постепенное развитие теории делимости
чисел привело к глубокому расширению
всей теории чисел.
1.1. Понятие
делимости.
Сумма, разность и произведение
целых чисел всегда является целым числом,
то есть, во множестве целых чисел всегда
выполнимы действия сложения, вычитания
и умножения. Иначе обстоит дело с делением.
Действие деления во множестве целых чисел
выполнимо не всегда.
Напомним, что разделить
целое число a на
целое число b –
это значит найти такое k, при
умножении которого на b получается a, то
есть bk=a.
Если для целых чисел a и b такое
целое число k существует,
то говорят, что a делится
на b.
Определение. Целое число
a делится на целое число b, не равное нулю,
если существует целое число k такое, что
a= bk.
Если a делится
на b, то b называется
делителем числа a.
Например, -48 делится
на 8, так как существует такое целое
число k, что
-48=8k, а именно k=-6;
число 35 не делится на 4, так как не существует
такого целого числа k, при
котором верно равенство 35=4 k.
Вместо «a делится
на b» говорят
также: «a кратно b», «число b –
делитель числа a», «число b делит a».
Обозначают: aïb (b делит a), aMb (a делится
на b).
Отметим, что предложение
«a делится
на b» представляет
собой некоторое высказывание о соотношении
между этими числами.
Замечание: Понятие делимости
относится только к целым числам. Для рациональных
чисел аналогичное понятие было бы бессодержательным,
так как для любых двух рациональных чисел a и b, где b¹0, всегда существует
рациональное число, являющееся их частным.
Поэтому в дальнейшем, говоря о делимости,
под «числом» будет подразумеваться целое
число.
Рассмотрим простейшие
свойства делимости. Для любых целых чисел a, b, c
справедливы следующие теоремы.
Теорема. Если
и с – частное от деления, то с – единственное.
Теорема.
Теорема. Если
и
, то
.
Теорема. Если
и
, то или a=b, или a = -b.
Теорема. Если
и
, то а=0.
Теорема. Если
и а¹0, то
.
Теорема. Для того
чтобы
необходимо и достаточно чтобы
.
Теорема. Если
, то
.
Теорема. Если сумма
чисел и к-1 слагаемое этой суммы делится
на некоторое число с, то и к-ое слагаемое
делится на с.
Свойства делимости
находят применение при решении задач.
Примеры:
1. Пусть a
делится на b и с делится на d. Выясним, делится
ли произведение ac на bd.
Решение: Из определения
делимости следует, что a= bk, с= dm,
где k и
m – целые числа. Отсюда aс=(bk)( dm)=(bd)( km).
Так как k и
m – целые числа, то km является
целым числом. Значит, существует такое
целое число, при умножении которого на bd в
произведении получается aс, то
есть по определению, aс делится
на bd.
2. Докажем,
что при любом натуральном n, большем 1,
число n
+4 является составным.
Решение: Разложим
сумму n
+4 на множители:
n
+4= n
+4+4n
-4 n
=( n
+2)
-(2n)
=( n
+2+2n)( n
+2-2n).
При nÎN и n>1
каждый из множителей является натуральным
числом, большим 1. Для первого множителя
это очевидно, для второго это модно доказать,
выделив из него квадрат двучлена: n
+2-2n= n
-2n+1+1=(n-1)
+1. Значит, при nÎN и n>1
число n
+4 емеет два натуральных делителя,
больших 1, то есть является составным
числом.
Глава II. Свойства
делимости.
Определение. Пусть
— целые числа. Говорят, что
число
делится на
, если
можно представить в виде
, где
— целое число.
Иначе:
— делитель
.
Обозначение:
.
Пусть
— целые числа, число
— простое.
1. Если в равенстве
два числа делятся на
, то и третье число делится на
.
2. Если
, то
.
3. Если
и
, то
.
4. Если
, то либо
, либо
.
Пример. Доказать, что если
и
, то и
.
Решение.
откуда
и
Глава III.
Деление с остатком.
Выше был описан случай,
когда говорят о так называемом делении
числа нацело, но так бывает далеко не
всегда, в этом случае рассматривают деление
с остатком.
Определение. Разделить
целое число a на целое число b с остатком
– это значит представить его в виде a=bq
+ r, где q и r целые числа, 0£r<ïbï.
Основную роль во всей арифметике целых
чисел играет теорема о делении с остатком.
Теорема. Для любых
целых a и b существует единственная пара
чисел q и r, удовлетворяющих условиям,
a=bq + r, 0£r<ïbï.
Замечание. В частности, если
, то
и
делится на
.
Замечание. Если
то q называется
неполным частным, а r – остатком
от деления a на b.
Из теоремы о делении с остатком следует,
что при фиксированном целом m>0 любое целое
число а можно представить
в одном из следующих видов:
При этом если
то будем иметь
, если
и
, если
.
Например, любое целое число
можно представить в виде
или
.
Любое целое число можно представить
в виде
,
или
.
Примеры:
1. Какой цифрой заканчивается
число 3
?
Решение: Так как число 3
оканчивается цифрой 1, то и любая
его степень вида (3
)
оканчивается цифрой 1. Найдём
остаток от деления числа 1995 на 4. Имеем
1995=4×498+3. Значит, 3
=(3
)
×3
. Первый множитель оканчивается
цифрой 1, а второй – цифрой 7. Значит, произведение
оканчивается цифрой 7, то есть число 3
оканчивается цифрой 7.
2. Какие остатки
могут получиться при делении квадрата
целого числа на 3?
Решение: Всякое число a в соответствии
с остатками от деления его на 3 может быть
представлено в одном из видов: a=3k, a=3k+1,
a=3k+2 (k–целое
число).
Соответственно получаем a
=9k
=3(3k
), a
=(3k+1)
=9k
+6k+1=3(3k
+2k)+1, a
=(3k+2)
=9k
+12k+4=3(3k
+4k+1)+1.
Мы видим, что число a
либо делится на 3, либо при делении
на 3 даёт остаток 1. Тем самым мы показали,
что квадрат целого числа при делении
на 3 не может дать остаток 2.
3. Докажем,
что, если остаток от деления числа на
9 есть 2, 3, 5, 6, 8, то это число не может быть
квадратом целого числа.
Решение: Рассмотрим
классы чисел, на которые разбивается
множество целых чисел при делении
на 9.
9k±1 (9k±1)
=81 k
±2×9k+1=9(9k
±2k)+1
9k±2 (9k±2)
=81 k
±4×9k+4=9(9k
±4k)+4
9k±3 (9k±3)
=81 k
±3×9k+9=9(9k
±2k)+1
9k±4 (9k±4)
=81 k
±4×9k+16=9(9k
±4k+1)+7
9k (9k)
=9×9k
При делении на 9 целые
числа, являющиеся полными квадратами
дают в остатке числа 0, 1, 4, 7. Следовательно,
числа, дающие в остатке 2, 3, 5, 6, 8 не могут
являться квадратами целых чисел.
Глава IV.
Простые и составные числа.
Определение 2.3. Целое положительное
число 1>р называется
простым, если оно имеет ровно два положительных
делителя: 1 и р.
Определение 2.4. Целое положительное
число m > 1 называется
составным, если оно имеет, по крайней
мере, один положительный делитель отличный
от 1 и m.
Примеры:
3 имеет ровно 2 делителя: 1 и 3, по определению 2.3, оно простое.
4 имеет своими делителями 1, 4 и 2, по определению 2.4, число 4 – составное.
Замечание 2.5. В соответствии
с определениями 2.3 и 2.4 все множество целых
положительных чисел можно разбить на
три подмножества: простые числа; составные
числа; 1.
Замечание 2.6. Существует
единственное простое четное число 2. Все
остальные четные числа являются составными.
Перечислим
основные свойства простых чисел.
Теорема 2.7. Если р и р1 –
простые числа и р
р1,
то р не
делится на р1,и р1 не
делится на р.
Теорема 2.8. Если произведение
нескольких целых чисел делится на простое
число р, то
по меньшей мере один из сомножителей
делится на р.
Теорема 2.9. Для любого
целого положительного числа n>1 наименьший,
отличный от единицы положительный делитель
всегда представляет собой простое число.
Теорема 2.10.(основная теорема арифметики). Всякое целое
положительное число, отличное от единицы,
может быть представлено в виде произведения
простых сомножителей и при том единственным
образом (с точностью до порядка следования
сомножителей).
Таким образом,
если m – целое
положительное число, а р1,
р2,
…рк- простые
числа, то m =
. Если, при этом, среди чисел р1,
р2,
…, рк есть
одинаковые, то можно записать каноническое
представление целого числа, представив
произведение одинаковых сомножителей
в виде степени:
m =
Мы выяснили,
что множество натуральных чисел можно
разбить на три подмножества. Встает вопрос
о числе простых чисел в бесконечном натуральном
ряду. Существуют ли простые числа среди
больших натуральных чисел, или с какого
то определенного числа все натуральные
числа, следующие за ним, будут составными?
Оказывается, что хотя в натуральном ряду
можно найти участки составных чисел любой
длины, множество простых чисел бесконечно.
Это утверждение было доказано ещё древнегреческим
математиком Евклидом и входит в его знаменитые
«Начала». Приведём здесь доказательство
этого утверждения:
Теорема 2.11. Множество
простых чисел бесконечно.
Доказательство. Доказательство
проведем от противного. Пусть множество
простых чисел конечно, и пусть р –
наибольшее простое число. Рассмотрим
натуральное число N, которое
является произведением всех простых
чисел, т.е.
и прибавим
к этому числу 1:
. Очевидно,
что полученное число не делится ни на
одно простое число от 1 до р, следовательно
получаем, что N = 1,
но непосредственно видно, что N >1.
Получили противоречие, которое возникло
из за того, что мы сделали неправильное
предположение. Следовательно, множество
натуральных чисел бесконечно.
Таким образом,
какую бы длинную серию последовательных
составных чисел мы ни встретили в ряду
натуральных чисел, мы можем быть убеждены
в том, что за нею найдется ещё бесконечное
множество простых чисел.
4.1.Свойства делимости чесел.
Делимость чисел обладает свойствами:
1. Если а и р- натуральные числа, причем р -простое, то либо а делится на р,
либо а и р взаимно просты.
Например 15и 11. 15и5.
2.Если М- общее кратное а и b,
а т - их наименьшее общее кратное, то М
делится на т.
Например,
3 и 5. Их кратное 90, наименьшее общее кратное
15, тогда 90 делится на 15.
3. Рефлексивность: если а делится на b, то и b делится на
а.
Это свойство
очевидно, как и то , что любое равенство
можно читать как справа налево, так и
слева направо
4. Транзитивность: если а делится на b и b делится
на с, то и а делится на с.
Разъясним
транзитивность нам конкретном примере:
36:12, 12:4, тогда и 36:4Кроме того, нетрудно
заметить, что делимость чисел практически
никак не связана с их величиной: существуют
маленькие числа, которые делятся на сравнительно
большое количество чисел. Например, 12
делится на 1, 2, 3, 4, 6, 12. И число 43 имеет только
два делителя: 1, 43.
Признаки делимости на 2
Необходимо
и достаточно, чтобы последняя цифра была
четной.
Например:
В числе 29654
последняя цифра 4 – она четная, значит,
число делится на 2.
Признаки делимости на 3
Для того чтобы
число делилось на 3, необходимо и достаточно,
чтобы
сумма его
цифр делилась на 3.
Например:
513 – 5+1+3=9,
значит, число делится на 3.
Признаки делимости на 4
Чтобы число
делилось на 4 надо
проверить
делится ли на 4 число из двух последних
цифр. Например:
1836 – 36:4, значит,
1836 делится на 4 без остатка.
Кроме этого
на 4 делятся числа, запись которых оканчивается
двумя нулями.
Например:
5500
^ Признаки
делимости на 5
Число делится
на 5 в том, и только в том случае если оно
оканчивается на
5 или на 0.
Например:
делится на пять.
Признаки делимости на 6
Чтобы проверить
делимость числа на 6, надо:
Число сотен умножить
на 2,
Полученный результат
вычесть из числа стоящего после числа
сотен.
Если полученный
результат делится на 6, то и все число
делится на 6. Например:
138 – число
сотен 1*2=2, 38-2=36, 36:6, значит, 138 делится на
6.
Признаки делимости на 7
Чтобы узнать
делится ли число на 7, надо: