§ 1. Предварительные сведения

В этом параграфе напомним основные факты о делимости целых чисел и сравнимости по модулю.

Если a, b  Z , b  0, то говорят, что b делит a или a кратно b, если a = bq для некоторого q  Z. В этом случае пишут a  b или b | a .

Примеры: 1. 156  52, т.к. 148 = 523.

2. –143 52, т.к. –143 = 52(–3) + 13, т.е. –143 даёт остаток 13 при делении на 52.

Упомянем важнейшие свойства делимости нацело:

1⁰. Если a | b и c | d , то ac | bd. В частности, верно a | bc, ac | |bc|, |ac| | bc , (±a) | (±b) при любой независимой друг от друга расстановке знаков у чисел a и b.

2⁰. Если a | b₁ , … , a | b_k , то a | (b₁c₁+ …+b_kc_k ) для любых целых чисел c₁ , … , c_k .

3⁰. Если a  0, b | a, то |b|  |a|. В частности у каждого ненулевого целого числа лишь конечное число делителей.

Пусть a₁ , … , a_n – целые числа, одновременно не равные нулю. Их общим делителем называется любое целое число d, делящее все указанные числа. Наибольший среди всех общих делителей не равных одновременно нулю целых чисел a₁ , … , a_n называется наибольшим общим делителем этих чисел и обозначается через НОД(a₁ , … , a_n) или (a₁ , … , a_n).

Примеры: НОД(0, 8) = 8, (12, 18) = 6, НОД(7, 9) = 1, (12, 40, 28) = 4, НОД(0, 0) не определён.

Общим кратным ненулевых целых чисел a₁ , … , a_n называется любое целое число, делящееся одновременно на каждое из указанных чисел. Наименьшее положительное кратное этих чисел называется их наименьшим общим кратным и обозначаемое символом НОК[a₁ , … , a_n] или просто через [a₁ ,… , a_n].

Примеры: НОК[0, 2] не определено, [24, 16] = 48, НОК[4, 6] = 24, НОК[8, 6, 30] = 120.

В дальнейшем, имея дело с НОД(a₁ , … , a_n) всегда будем молчаливо предполагать, что целые числа a₁ , … , a_n одновременно не равны нулю, а имея дело с НОК[a₁ , … , a_n] – что целые числа все a₁ , … , a_n ненулевые.

Напомним важнейшие свойства наибольшего общего делителя и наименьшего общего кратного:

1⁰. НОД(a₁ , … , a_n) и НОК[a₁ , … , a_n] определёны однозначно.

2⁰. Для произвольной перестановки (i₁ , … , i_n) символов 1, … , n справедливы равенства

НОД(a₁ , … , a_n) = НОД(), НОК[a₁ , … , a_n] = НОК[].

3⁰. Справедливы равенства

НОД(a₁ , … , a_n) = НОД(±a₁ , … , ±a_n), НОК[a₁ , … , a_n] = НОК[±a₁ , … , ±a_n]

при любых знаках в правых частях.

4⁰. Если a | b, то НОД(a, b) = |a|, НОК[a, b] = |b|.

5⁰. Для произвольного t  Z справедливы равенства

НОД(a, b) = НОД(a, b – at) = НОД(a – bt, b).

6⁰. Любой общий делитель d целых чисел а₁ , … , a_n делит их наибольший общий делитель НОД(a₁ , … , a_n), любое общее кратное K целых чисел а₁ , … , a_n делится на их наименьшее общее кратное НОК[а₁ , … , a_n].

11⁰. Справедливо равенство НОК[a, b] = .

Замечание. Обобщение НОК[a₁ , … , а_n] = доказанной формулы на случай любого числа сомножителей неверно. Например,

НОК[2, 4, 6] = 12  = 24.

12⁰. Справедливы формулы

(a₁ , … , a_n) = ((a₁ , … , a_n–1), a_n), [a₁ , … , a_n] = [[a₁ , … , a_n–1], a_n],

из которых следует, в частности, что вычисление НОД(a₁ , … , a_n) и НОК[a₁ , … , а_n] сводится к последовательному вычислению аналогичных величин для двух чисел:

(a₁ , … , a_n) = (((…((a₁ , a₂), a₃), … ), a_n–1), a_n).

[a₁ , … , a_n] = [[[…[[a₁ , a₂], a₃], … ], a_n–1], a_n].

14⁰. Для любого ненулевого с  Z верны формулы

НОД(ca₁ , … , ca_n) = |c|НОД(a₁ , … , a_n),

НОК[ca₁ , … , ca_n] = |c|НОК[a₁ , … , a_n].

Как известно, НОД(a, b) удобно вычислять с помощью алгоритма Евклида.

Примеры: 1. Вычислить НОД(244, 356).

_ 356 |244

244 1

_ 244 |112

224 2

_ 112 | 20

100 5

_ 20 |12

12 1

_ 12 | 8

8

_ 8 | 4

8 2

0

Таким образом, НОД(244, 356) = 4 – последнему ненулевому остатку в алгоритме Евклида.

2. Вычислить НОД(244, 356, 96).

Имеем НОД(244, 356, 96) = ((244, 356), 96) = (4, 96) = 4.

3. Вычислить НОК[35, 50, 20].

Имеем НОК[35, 50, 20] = [[35, 20], 50] = = [140, 50] = = 700, т.к. НОД(35, 20) = 5НОД(7, 4) = 51 = 5 и [140, 50] = 10[14, 5] = = 1070 = 700.

Целые числа a₁ , … , a_n называются взаимно простыми (в совокупности), если НОД(a₁ , … , a_n) = 1. Они называются попарно взаимно простыми в случае, когда НОД(a_i , a_j) = 1 (1  i < j  n).

Примеры: 1. Числа 6, 4, 3 взаимно просты в совокупности, но не попарно.

2. Числа 6, 11, 35 попарно взаимно просты.

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

Лемма (основное свойство двух взаимно простых чисел). Если целые числа a, b взаимно просты и a | bc, где с  Z, то a | c.

Доказательство. Утверждение очевидно, если a = ±1. В противном случае из НОД(a, b) = 1 получаем, во-первых, b  0 (иначе НОД(a, b) = |a| > 1), а во-вторых, НОК[a, b] = = |ab| . С другой стороны, bc  b и bc  a, т.е. bc – общее кратное чисел a, b, а значит, по свойства делимости делится нацело на НОК[a, b] = |ab| = ±ab. Таким образом, bc = abq для некоторого целого q, т.е. c = aq и a | c.

Лемма доказана.

Следствие 1. Если целое число a взаимно просто с b₁ , … , b_n и для некоторого c  Z a делит b₁…b_nc, то a | c.

Доказательство. Постепенно уменьшаем число сомножителей: из условий a | b₁…b_nc и НОД(a, b₁) = 1 следует по лемме a | b₂…b_nc . Продолжая этот процесс, на некотором шаге получим a | b_nc и НОД(a, b_n) = 1, откуда по лемме a | c .

Следствие 1 доказано.

Следствие. Целое число взаимно просто с каждым из нескольких целых чисел тогда и только тогда, когда оно взаимно просто с их произведением.

Доказательство. Если целое число a взаимно просто с каждым из нескольких целых чисел b₁ , … , b_n , и НОД(a, b₁…b_n) = D, то D взаимно просто с каждым b_i (1  i  n): любой общий делитель D и b_i является общим делителем a и b_i , т.е. равен ±1. Поэтому D | b₁…b_n1, и по следствию 1, D | 1, т.е. D = 1, что и требовалось.

Обратно, если a взаимно просто с b₁…b_n , то любой общий делитель a и b_i будет общим делителем a и b₁…b_n , т.е. a взаимно просто с b_i (1  i  n).

Следствие 2 доказано.

Натуральное число p называется простым, если оно имеет ровно два различных натуральных делителя 1 и p.

Примеры: 1. Числа 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37 – простые.

2. Числа –2, 0, 1, 4, 9, 10, 15, – не простые.

Напомним наиболее важные свойства простых чисел.

1⁰. Любые два различных простых числа взаимно просты.

2⁰. Для целого числа a и простого p верно НОД(a, p) > 1  a  p.

3⁰. Простое число делит произведение нескольких целых чисел тогда и только тогда, когда оно делит один из сомножителей.

Основная теорема арифметики. Любое целое число n, модуль которого больше 1, единственным образом записывается в виде канонического произведения , гдеk  1, ±  {+ , –}, p_i – простые числа, _i  N и p₁ < … < p_k .

Пример: Найдём каноническое разложение числа –6230840.

Последовательно делим число n = 6230840 на простые числа:

Таким образом, 6230840 = 2³57²1117², а –6230840 = –2³57²1117². Здесь и далее первые степени простых чисел не пишем.

Следствие (о взаимно простых сомножителях степени). Если имеется разложение n^k = m₁…m_s степени целого числа n в произведение попарно взаимно простых целых ненулевых сомножителей m₁ , … , m_s , то эти сомножители, с точностью до знака, являются k-ми степенями некоторых попарно взаимно простых чисел. Более точно: m_i = _iu_i^k , где _i  {–1, 1}, u_i  N , НОД(u_i , u_j) = 1 (1  i  s, 1  j  s), |n| = u₁…u_s , ₁…_s = .

Доказательство. Запишем m_i = _i|m_i| , где _i = 1, если m_i > 0 и _i = –1, если m_i > 0 (1  i  s), и аналогично n = |n|. Тогда, очевидно, получается равенство  ^k|n|^k = (₁…_s)|m₁|…|m_s|, откуда = =  ^k = ₁…_s , |n|^k = = |m₁|…|m_s| . При этом все модули являются натуральными числами, так что осталось доказать утверждение для натуральных чисел.

Пусть n, m₁ , … , m_s  N имеют разложения , (1  i  s) в произведения простых чисел, где выполнены неравенства p₁ < … < p_f , а r_ij – простые числа, не встречающиеся среди p₁ , … , p_f . Тогда . Переставляя простые числа в правой части (собирая их в степени с одинаковыми основаниями), получим в левой и правой частях равенства канонические разложения, которые должны быть одинаковыми по основной теореме арифметики. Это показывает, что в правой части должны отсутствовать сомножители r_ij (1  j  t_i , 1  i  s), а показатели степеней при простом числе p_ в левой и правой частях равны: k_ = (1   f).

Таким образом, , причём ввиду попарной взаимной простоты чисел m₁ , … , m_s каждое простое число p_i (1  i  f) участвует лишь в

одном из разложений чисел m₁ , … , m_s . Поэтому

,

где _ = _1 + … + _s , но на самом деле в этой сумме лишь одно ненулевое слагаемое. Значит, сравнивая показатели степеней при p_ в левой и правой частях равенства, по основной теореме арифметики заключаем, что каждая степень _ij делится на k : _ij = k_ij для некоторого натурального или нулевого _ij (1  i  s, 1  j  f).

Итак, , т.е. u_i = (1  i  s). Эти числа попарно взаимно просты, т.к. любой общий делитель двух из них u_i , u_j будет общим делителем взаимно простых чисел m_i , m_j , а значит, равен ± 1.

Следствие доказано.

Наконец, напомним простейшие сведения из теории сравнений. Два целых числа a, b называются сравнимыми по модулю m  Z \ {0}, если a – b  m.

Примеры: 8  2 (mod 3), т.к. 8 – 2 = 32, –27 12 (mod 5), т.к. разность –27 – 12 = –39 не делится нацело на 5.

Упомянем некоторые важнейшие свойства сравнений.

1⁰. Числа a и b сравнимы по модулю m тогда и только тогда, когда они дают одинаковые остатки при делении на m.

2⁰. Условия a  b и a  0 (mod b) эквивалентны.

3⁰. Любое целое число a сравнимо само с собой по любому модулю m (рефлексивность отношения сравнимости).

4⁰. Если a  b (mod m), то b  a (mod m) (симметричность отношения сравнимости).

5⁰. Если a  b (mod m) и b  с (mod m), то a  c (mod m) (транзитивность отношения сравнимости).

6⁰. Если a  b (mod m), то для любого целого числа c справедливо

a ± c  b ± c (mod m) , ac  bc (mod m).

7⁰. Если a  b (mod m) и c  d (mod m), то a ± c  b ± d (mod m).

8⁰. Если a  b (mod m) и c  d (mod m), то ac  bd (mod m).

9⁰. Если a  b (mod m), то для любого натурального k верно сравнение a^k  b^k (mod m).

10⁰. Если целые числа a, b, m делятся нацело на число d  Z \ {0}, то a  b (mod m) тогда и только тогда, когда .

11⁰. Если da  db (mod m) и НОД(d , m) = 1, то a  b (mod m).

Сравнения дают удобный язык для изучения делимости чисел. Связь сравнений с делимостью выявлена в свойстве 2⁰.

Примеры: 1. Вычислить остаток числа a⁴ – 8a³ + 19 при делении на 23, если известно, что a даёт при делении на 23 остаток 5.

Если a  5 (mod 23), то

a⁴ – 8a³ + 19  (a²)² – 8aa² + 19  2² – 852 + 19 

 – 402 + (2² + 19)  –(–6)2 + 0  12 (mod 23),

т.е. искомым остатком будет 12.

2. Вычислить 18¹⁰⁰ + 20 (mod 25).

18¹⁰⁰ + 20  (–7)¹⁰⁰ – 5  (7²)⁵⁰ – 5  (–1)⁵⁰ – 5 

 1 – 5  –4  21 (mod 25).

Таким образом, не вычисляя числа 18¹⁰⁰ + 20, можно сказать, что остаток этого числа при делении на 25 равен 21.

3. Найти младшую цифру числа 24³⁵ – 18 .

Нужно вычислить . Имеем

24³⁵ – 18  4³⁵ – 8  (4²)¹⁷4 – (–2)  6¹⁷4 + 2  64 + 2  4 + 2 = 6 (mod 10).

Здесь использован тот факт, что младшая цифра числа 6^k равна 6, т.е. 6^k  6 (mod 10). Таким образом, искомой младшей цифрой будет 6.