d не делит а, пишут d\ а.

Обычно перечисляют только положительные делители; например, делители числа 24 - это числа 1, 2, 3, 4, 6, 8, 12 и само число 24.

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

Число а, не имеющее делителей, кроме ±1 и ±а, называется простым (prime); таковы числа

2, 3, 5, 7,11,13,17,19, 23, 29, 31, 37,41,43, 47, 53, 59,... .

Простых чисел бесконечно много (упр. 33.1-1). Целое число а > 1, не являющееся простым, называется составным (composite). Число 1, число 0, а также отрицательные целые числа мы не относим ни к простым, ни к составным.

Деление с остатком. Сравнения по модулю.

Фиксируем целое число п. Все целые числа делятся на п групп в зависимости от остатков, которые они дают при делении на п: числа вида кп (кратные п) образуют одну группу, числа вида кп-\-1 - другую и т.п.

Строго говоря, тут следует сослаться на такую теорему (подробности можно найти в учебнике по теории чисел, например, в книге Нивена и Цукермана [151]):

Теорема 33.1 (о делении с остатком)

Для любого целого числа а и положительного целого числа п существует единственная пара целых числа q и г, для которых 0 г < п ж а = qn -\- г.

Число q = [а/п\ называется частным (quotient); число г, обозначаемое a mod п, называется остатком (remainder, residue). Очевидно, что п а тогда и только тогда, когда a mod п = 0, что

а = [а/п\п + (a mod п)(33.1)

и что

a mod п = а - [а/п\п.(33.2)

Говорят, что а сравнимо с Ь по модулю п (a is equivalent to b, modulo га; запись: a = b (mod га)) если (a mod n) = (b mod га), то есть га I (b - а). Если а не сравнимо с b по модулю га, пишут а ф b (mod га). Например, 61 = 6 (mod 11) и -13 = 22 = 2 (mod 5).

Все целые числа делятся на га классов эквивалентности по модулю га (eqivalence classes modulo га). Число а входит в класс

[а]п = {а + кп : к £ z}.

Например, [3]7 = [-4]7 = [10]7 = {... , -11, -4, 3,10,17,...}. Множество всех классов эквивалентности по модулю га обозначается

Ъп = {[а]п : 0 а га - 1}.(33.3)

Выбирая в каждом классе по представителю, можно считать, что

Zn = {0,1,..., п-1}.(33.4)

Общие делители. Наибольший общий делитель.

Среди всех общих делителей (common divisors) данных чисел а и Ь можно выбрать наибольший общий делитель, (greatest common divisor), который обозначают gcd(a, b) или НОД(а, Ъ) (он определён, если хотя бы одно из чисел а и Ь отлично от 0; положим для удобства gcd(0, 0) = 0.

Важные свойства общих делителей и наибольшего общего делителя:

если d а и d \ Ь, то d \ (а + Ъ) и d \ (а - Ъ).(33.5)

если d а и d \ Ь, то d \ (ах + by),(33.6)

при любых целых хну. Если а \ Ь то \а\ \Ь\ или 6 = 0, поэтому

если а Ь и Ь \ а, то а = ±6.(33.7)

gcd(a, Ъ) = gcd(6, а)(33.8)

gcd(a, Ъ) = gcd(-a, Ъ),(33.9)

gcd(a,6) = gcd(a, \Ъ\),(33.10)

gcd(a,0) = \а\,(33.11)

gcd(a,A;a) = \а\ при всяком к £ z.(33.12)

Теорема 33.2

Наибольший общий делитель целых чисел а и Ь, не равных 0 одновременно, является наименьшим положительным элементом множества {ах + by : х,у £ z} целочисленных линейных комбинаций чисел а и Ь.

Доказательство. Пусть наименьший положительный элемент этого множества равен s. Тогда s = ах + by для некоторых х,у £ Z. Положим q = [a/s\. Согласно (33.2),

a mod s = а - qs

= а - q(ax + by)

= а(1 - qx) + b(-qy),

и потому остаток от деления а на s тоже является линейной комбинацией а и Ь. Но s был наименьшей положительной комбинацией такого вида, так что a mod s = 0 и s \ а. По аналогичным причинам верно s Ь. Таким образом, s является общим делителем а

и Ь, поэтому gcd(a,6) s. С другой стороны, gcd(a,6) делит как

a,так и Ь, а потому делит и s = аж + 6у (33.6). Поскольку s > О, отсюда следует, что gcd(a,6) s. Таким образом, gcd(a,6) s и gcd(a, 6) s, так что gcd(a, Ъ) = s,

Следствие 33.3

Наибольший общий делитель двух целых чисел кратен любому их общему делителю. Доказательство.

По теореме 33.2 gcd(a,6) является линейной комбинацией а и Ь. Следствие 33.4

Для любых целых чисел а и Ь и неотрицательного целого числа га выполняется соотношение gcd(ara, Ьп) = raged (а, Ь).

Доказательство. Элементы вида агаж + Ьпу получаются из элементов вида ах + by умножением на га, так что это относится и к наименьшему элементу такого вида.

Следствие 33.5

Для любых положительных целых чисел га, а и Ь из га аЬ и gcd(a, га) = 1 следует га Ь. Доказательство

оставляется читателю (упр. 33.1-4). Взаимно простые числа.

Целые числа а и Ь взаимно просты (are relatively prime), если gcd(a, b) = 1. Теорема 33.6

Если gcd(a,p) = 1 и gcd(6,p) = 1, то НОД(аЬ,р) = 1 (для любых целых чисел a,b,p).

Доказательство. По теореме 33.2 найдутся целые числа ж, у, х и у, для которых

ах + ру = 1, Ьх1 + ру1 = 1.

Перемножая эти равенства, мы видим, что

ab(xx) + p(ybx + у1 ах + руу) = 1,

так что 1 является целочисленной линейной комбинацией аЬ и р; осталось сослаться на теорему 33.2.

Целые числа щ, п2, ,пк называются попарно взаимно простыми (pairwise relatively prime), если любые два из них взаимно просты.

Разложение на простые множители Теорема 33.7

Если простое число р делит произведение двух целых чисел а и

b,то р а или р Ь.

Доказательство. Если это не так и р не делит ни а, ни Ь, то Р взаимно просто с этими числами (других делителей у р нет), и потому взаимно просто с их произведением (теорема 33.6).