algebra.1semestr.lectures1-16

1. Лекция 1

L1

Напомним, что N обозначает множество всех натуральных чисел. Нам будет удобно считать, что натуральные числа начинаются с единицы: N = f1; 2; 3; : : : g.1

1.1. Принцип математической индукции.

Лемма 1. Любое непустое подмножество S µ N содержит наименьший элемент.

Доказательство. Поскольку S не пусто, оно содержит хотя бы один элемент m1 2 S. Если m1 наименьший элемент в S, то все доказано. Иначе S содержит элемент m2 меньший m1. В частности, множество S1 = fn 2 S j n < m1g непусто. Но это множество является подмножеством конечного множества 1; : : : ; m1 ¡ 1, поэтому конечно. Выберем наименьший элемент m в S1. Ясно, что он будет наименьшим элементом в S. ¤

Теорема 2. (Принцип математической индукции) Пусть S некоторое свойство натуральных чисел. Предположим, что

1)S(1) верно, и

2)для любого натурального k из выполнимости S(k) вытекает выполнимость S(k +1). Тогда S(n) верно для любого n 2 N.

Доказательство. Иначе множество T = fn 2 N j S(n) не выполняется g не пусто. По предыдущей лемме мы заключаем, что T имеет наименьший элемент l. Из пункта 1) вытекает, что l > 1, поэтому k = l ¡ 1 2 N. Но тогда l ¡ 1 2= T , следовательно выполняется S(k). По пункту 2) заключаем, что верно S(l). Но это противоречит условию l 2 T .2 ¤

Пример 3. Докажем, используя принцип математической индукции, следующую формулу:

1 + 2 + ¢ ¢ ¢ + n = n(n + 1) : 2

Поскольку 1 = 12¢2 , то эта формула верна для n = 1 (базис индукции). Чтобы осуществить шаг индукции, предположим, что написанная выше формула верна (для n), а нам нужно доказать ту же формулу для n + 1, то есть проверить, что

1 + 2 + ¢ ¢ ¢ + (n + 1) = (n + 1)(n + 2) : 2

Действительно,

1 + 2 + ¢ ¢ ¢ + (n + 1) = (1 + 2 + ¢ ¢ ¢ + n) + (n + 1) = n(n + 1) + n + 1 ; 2

и нетрудно проверить, что последнее выражение равно (n + 1)(n + 2)=2.

Упражнение 4. Докажите, что 1 + ¢ ¢ ¢ + n2 = n(n + 1)(2n + 1).

6

1То, что нуль первое натуральное число, также распространенная точка зрения.

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

1

1.2. Свойства делимости целых чисел. Напомним, что символ Z обозначает целые числа: Z = f0; §1; §2; : : : g.

Определение 5. Пусть a; b 2 Z, b =6 0. Мы скажем, что b делит a (записывается b j a), если a = br для некоторого целого r. Заметим, что это эквивалентно тому, что a=b = rцелое число. Например, 2 j 4, поскольку 4=2 = 2 2 Z, но 3 - 5, потому что 5=3 2= Z.

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

Лемма 6. 1) Если b =6 0, то b j 0.

2)Если a j b и b j a (для a; b =6 0), то a = §b.

3)Если a j b и b j c, то a j c (транзитивность).

4)Если a j b и a j c, то a j (b + c).

Доказательство. 1) b ¢ 0 = 0.

2) По определению делимости a = br и b = as для целых r; s. Тогда a = br = asr влечет (поскольку a 6= 0) 1 = sr, то есть либо s = r = 1, либо s = r = ¡1.

3) По условию b = ar и c = bs для r; s 2 Z, следовательно ars = c, откуда a j c.

4) Имеем b = ar и c = as. Но тогда a(r + s) = ar + as = b + c, следовательно a j b + c. ¤

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

Следствие 7. Пуcть c = a1 +¢ ¢ ¢+an = b1 +¢ ¢ ¢+bm, причем все слагаемые, за исключением самое большее одного, делятся на d. Тогда и вся сумма делится на d.

Доказательство. Действительно, по условию и симметрии можно считать, что все ai де-

0 · r < jbj такие, что a = b¢q+r, причем q и r определяются этими условиями однозначно. При этом q называется частным, а r остатком (при делении a на b).

Доказательство. Для простоты предположим, что b > 0 (проверьте, что поменяется в рассуждениях ниже, если b < 0!). Ясно, что полуинтервалы [bq; bq + b) (точнее целые точки в них) образуют разбиение Z:

Итак, найдется ровно одно такое q 2 Z, что bq · a < bq + b. Тогда это q и r = a ¡ bq искомые.

Единственность вытекает из рисунка. Или можно рассуждать так: пусть a = bq + r = bq1 + r1, где 0 · r; r1 < jbj. Тогда из b(q ¡ q1) = r1 ¡ r следует r1 = r и q1 = q. ¤

1.3. Наибольший общий делитель, алгоритм Евклида. Пусть a и b целые положительные числа. Наибольшим общим делителем a и b, НОД(a; b), называется наибольшее (положительное) число, которое делит и a и b. Заметим, что любой делитель чисел a и b не превосходит a и b, поэтому НОД(a; b) · a; b (в частности, НОД(a; b) существует).

Например, НОД(2; 4) = 2 и НОД(12; 21) = 3.

2

Замечание 9. Если a j b, то НОД(a; b) = a.

Доказательство. Пусть x = НОД(a; b). По сказанному выше, x · a. С другой стороны, поскольку a j a; b, то a · x по определению наибольшего общего делителя. Итак, x = a. ¤

abc Лемма 10. Если a = bq + c, то множество общих делителей a и b совпадает с множеством общих делителей b и c. В частности, НОД(a; b) = НОД(b; c).

Эта теорема позволяет эффективно уменьшать числа, вычисляя их наибольший общий делитель.

tПример 11. Вычислить НОД(1001; 390).

Решение. Обозначим x = НОД(1001; 390). Разделим 1001 на 390 с остатком: 1001 = 390 ¢ 2 + 221. По только что доказанной лемме x = НОД(390; 221). Имеем 390 = 221 ¢ 1 + 169, откуда x = НОД(221; 169).

Разделим теперь 221 на 169:

Аналогичный алгоритм имеет место и в общем случае. Пусть a ¸ b > 0 целые числа и мы хотим найти их НОД. Разделим a на b с остатком:

a = bq1 + r1, 0 · r1 < b.

Если r1 = 0, то НОД(a; b) = b. Иначе НОД(a; b) = НОД(b; r1). Если r1 j b, то НОД(b; r1) = r1, в противном случае b = r1q2 + r2, 0 < r2 < r1. Продолжая деление, мы получаем строго убывающую последовательность остатков r1 > r2 > : : : . Поскольку этот процесс может продолжаться только конечное число шагов, мы найдем НОД(a; b). Заметим, что НОД будет равен последнему ненулевому остатку в процессе деления.

Этот алгоритм называется алгоритмом Евклида.

uv Теорема 12. Если d = НОД(a; b), то найдутся u; v 2 Z такие, что d = au + bv.

Доказательство. Без ограничения общности можно предположить, что a ¸ b. Если b j a, то есть a = br, то НОД(a; b) = b, и достаточно положить u = 0, v = r.

Иначе a = bq + r, 0 < r < b, следовательно по индукции (например, по числу шагов в алгоритма Евклида) существуют u0; v0 2 Z такие, что НОД(b; r) = bu0 + rv0. Но тогда

Пример 13. Представить НОД(1001; 390) = 13 в виде 1001u + 390v.

Решение. Сокращая на 13 достаточно найтиtu и v такие, что 77u + 30v = 1. Перепишем все строчки из алгоритма деления (см. пример 11), сокращая их на 13:

77 = 30 ¢ 2 + 17 ;

3

30 = 17 ¢ 1 + 13 ;

17 = 13 ¢ 1 + 4 ;

13 = 4 ¢ 3 + 1.

Из последнего равенства запишем 1 = 13¡4¢3. Теперь заменим 4 на 17¡13¢1 из третьего равенства:

1= 13¡(17¡13¢1)¢3 = 13¢4¡17¢3. Далее заменим 13 на 30¡17¢1 из второго равенства:

1= (30¡17¢1)¢4¡17¢3 = 30¢4¡17¢7. Наконец подставим 77¡30¢2 вместо 17, используя первое равенство:

1= 30 ¢ 4 ¡ (77 ¡ 30 ¢ 2) ¢ 7 = 30 ¢ 18 ¡ 77 ¢ 7 (проверьте это равенство!), то есть можно взять

gcd-same Следствие 14. Множество общих делителей a и b совпадает с множеством делителей c = НОД(a; b).

Доказательство. Если d j c, то (поскольку c j a; b) заключаем, что d j a; b.

uv Предположим, что d j a; b. Разделим c на d с остатком: c = dq + r, 0 · r < d. По теореме 12 запишем c = au + bv. Тогда в равенстве au + bv = dq + r, слагаемые a; b; d делятся на d, следовательно r делится на d. Из r < d вытекает r = 0, поэтому d j c. ¤

2. Лекция 2

L2

Определим НОД(a1; : : : ; an) как наибольший общий делитель (натуральных) чисел a1; : : : ; an.

Лемма 15. НОД(a; b; c) = НОД(a;НОД(b; c)).

gcd-same

Доказательство. По следствию 14, d j b; c если и только если d j НОД(b; c). Поэтому левые и правые части нашего равенства имеют один и тот же набор делителей, а значит совпадают.

¤

Например, НОД(12; 9; 45) = НОД(12; 9) = 3.

Аналогично, рассуждая по индукции (проведите это рассуждение самостоятельно!), доказывается следующая рекуррентная формула.

Предложение 16. НОД(a1; : : : ; an) = НОД(a1;НОД(a2; : : : ; an)).

Скажем, что числа a1; : : : ; an взаимно просты, если НОД(a1; : : : ; an) = 1, то есть a1; : : : ; an не имеют нетривиальных (> 1) общих делителей. В этом случае пишем (a1; : : : ; an) = 1.

Например 12 и 35 взаимно просты, а 12 и 18 нет (поскольку оба делятся на 3). По uv

теореме 12 (a; b) = 1 если и только если au + bv = 1 для некоторых (целых) u и v. Аналогичное утверждение верно и для произвольного набора целых чисел (сформулируйте его и докажите по индукции!).

abc Лемма 17. Пусть a; b; c 2 N такие, что c j ab и (c; a) = 1. Тогда c j b.

Доказательство. Мы знаем, что au+cv = 1 для некоторых u и v. Домножая это равенство на b, получаем b = abu + cbv. Поскольку c j abu и c j cbv, то заключаем, что c j b. ¤

4

2.1. Наименьшее общее кратное.

Определение 18. Наименьшим общим кратным НОК(a; b) двух натуральных чисел a и b называется наименьшее среди чисел c таких, что a j c и b j c (то есть c кратно и a и b).

Заметим, что a; b j ab, поэтому множество общих кратных a и b непусто, следовательно имеет наименьший элемент (· ab). Однако в общем случае НОК(a; b) =6 ab. Например,

Доказательство. Пусть x = НОД(a; b) и y = НОК(a; b); нам нужно доказать, что xy = ab. Заметим, что a = a1x, b = b1x, причем (a1; b1) = 1. Нужно проверить, что

y= НОК(a; b) = ab = a1x ¢ b1x = a1b1x : x x

Заметим, что a; b j a1b1x (= ab1 = a1b), поэтому y · a1b1x.

Осталось проверить, что если y ¸ a1b1x. На самом деле мы покажем, что a1b1x j y. Действительно, имеем y = c1a для некоторого c1, следовательно y = c1a1x. Аналогично

Мы доказали несколько больше.

Следствие 21. Множество общих кратных чисел a и b совпадает с множеством кратных НОК(a; b).

Как обычно, аналогичное утверждение верно и для любого набора a1; : : : ; an натуральных чисел (сформулируйте это утверждение!).

Заметим, что в общем случае НОК(a; b; c) =6

5

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

Определение 22. Натуральное число p > 1 называется простым, если единственными делителями p являются 1 и p (отметим, что 1 не считается простым числом).

Например, 7 простое число, а 4 = 2 ¢ 2 составное (т.е. не простое). Запишем первые простые числа: p1 = 2, p2 = 3, p3 = 5 и т.д. Простой метод нахождения простых чисел следующий. Возьмем p1 = 2. Все остальные кратные двойки: 2; 4; 6; : : : не являются простыми числами, вычеркнем их (вместе с 2). Первое оставшееся в списке число 3 будет простым. Вычеркнем из нашего списка все числа 3; 6; 9; 12; : : : и т.д. Этот метод "просеивания" чисел для нахождения простых называется "решетом Эратосфена"3.

Не вычеркнем ли мы все простые числа после конечного числа шагов, то есть конечно или бесконечно множество простых чисел?

Лемма 23. Наименьший, отличный от 1, делитель любого натурального числа n > 1 является простым числом.

Доказательство. Предположим, что p не простое, то есть p = p1p2, где p1; p2 > 1, в частности p1 < p. Запишем n = pm для некоторого m, следовательно m = p1(p2m). Но тогда

Доказательство. Иначе все простые числа можно перенумеровать в порядке возрастания p1; p2; : : : ; pn. Пусть n = p1 ¢ p2 ¢ ¢ ¢ ¢ pn + 1 и пусть p наименьший отличный от 1 делитель n. Мы знаем, что p простое число, следовательно p = pi для некоторого i. Но тогда p j n и p j p1 ¢ ¢ ¢ ¢ ¢ pn влечет p j 1, что невозможно. ¤

К сожалению, алгоритм, предлагаемый решетом Эратосфена, не позволяет (в реальное время) найти "очень большие" простые числа. Более того, теоретически эффективный алгоритм для распознавания, является ли данное число простым, был открыт совсем недавно, но пока и он имеет ограниченный спектр практического применения.

Самые большие из известных простых чисел были найдены, используя числа Мерсенна.4 А именно, Мерсенн заметил, что числа 2n ¡1 составные, если n составное число. Если p простое, то число Mp = 2p ¡ 1 (называемое числом Мерсенна) часто оказывается простым. Например M2 = 22 ¡ 1 = 3, M3 = 23 ¡ 1 = 7, M5 = 25 ¡ 1 = 31 простые (попробуйте сами найти первое не простое число Мерсенна). Существует довольно эффективный метод (критерий Люка–Лемера), который позволяет проверять, является ли Mp простым числом.

Используя этот алгоритм и суперкомпьютер, в 2008 г. специалисты UCLA5 проверили простоту M43112609, числа, которое имеет 12978189 цифр.6

3по имени греческого математика, астронома и поэта Эратосфена Киренского (276–194 г. до н.э.) 4Марин Мерсенн французский любитель математики XVII века.

5University of California, Los Angeles

6авторы этого открытия получили часть премии в $100000, назначенной Electronic Frontier Foundation, за нахождение простого числа с 10 миллионами цифр.

6

Совсем недавно (в январе 2013 г.) в рамках проекта Great Internet Mersenne Prime Search было проверено, что число M57885161 также простое. Это наибольшее известное простое число имеет 17425170 цифр.

Теорема 25. Любое натуральное число n > 1 единственным образом записывается в виде n = pn11 ¢ : : : ¢ pnkk , где p1 < ¢ ¢ ¢ < pk простые числа.

Такое представление n в виде произведения степеней простых чисел называют каноническим разложением n.

Доказательство. Докажем сначала существование такого разложения. Для n = 2 утверждение очевидно. Для больших n, применяя индукцию, мы можем считать, что для чисел меньших n нужное представление существует.

Запишем n = pm, где p > 1 наименьший (следовательно простой) делитель n. По индукции мы знаем, что m = pn11 ¢ : : : ¢ pnkk , причем p · p1 < : : : < pk по построению. Если

p< p1, то n = p¢pn11 ¢: : :¢pnkk нужное разложение, иначе (т.е. если p = p1) n = pn11+1 ¢: : :¢pnkk . Чтобы доказать единственность, нам потребуется следующая лемма.

Вернется теперь к доказательству единственности. Ясно, что достаточно проверить следующее:

если p1 ¢: : : ¢pk = q1 ¢: : : ¢ql для простых чисел pi и qj, то существует взаимно однозначное отображение f из множества f1; : : : ; kg в множество f1; : : : ; lg такое, что pi = qf(i).

Поскольку p1 делит левую часть равенства, то оно делит его правую часть. По только что доказанной лемме получаем, что p1 j qj, следовательно p1 = qj для некоторого j. Тогда

Мы скажем, что a сравнимо с b по модулю m, если m j a ¡ b, то есть a ¡ b = mx для некоторого x 2 Z.

Свойства сравнений.

1)a ´ a (mod m).

2)Если a ´ b (mod m), то b ´ a (mod m).

3)Если a ´ b (mod m) и b ´ c (mod m), то a ´ c (mod m).

4)Если a ´ b (mod m) и c ´ d (mod m), то a + c ´ b + d (mod m) и ac ´ bd (mod m).

5)Если (d; m) = 1 и da ´ db (mod m), то a ´ b (mod m).

Доказательство. 1) Так как a ¡ a = 0 = 0 ¢ m. 2) Из a ¡ b = mx вытекает, что b ¡ a = m(¡x).

7

3)Имеем a ¡b = mx и b ¡ c = my для некоторых x; y 2 Z. Тогда a ¡ c = (a ¡b) + (b ¡c) = m(x + y).

4)Докажем только вторую часть утверждения. По предположению a¡b = mx и c¡d = my для некоторых x; y 2 Z. Тогда ac = (b+mx)(d+my) = bd+m(by +mxy +xd), следовательно

Определение 27. Пусть a 2 Z. Множество всех (целых) чисел x таких, что x ´ a (mod m) называется классом вычетов a по модулю m, и обозначается a.

Например, пусть a = 1 и m = 2. Тогда условие x ´ 1 (mod 2) означает 2 j x ¡ 1, т.е. x = 2y + 1 нечетное число. Итак, класс вычетов 1 по модулю 2 состоит из всех нечетных чисел.

Лемма 28. a = fa + my j y 2 Zg.

Доказательство. Ясно, что a+my ´ a (mod m), т.е. правая часть является подмножеством левой.

Чтобы проверить обратное включение, возьмем произвольное x 2 a. Это значит, что x ´ a (mod m), т.е. x ¡ a = my для y 2 Z, а тогда x = a + my принадлежит множеству в

элементов Z по модулю 2.

Предложение 29. a ´ b (mod m) если и только если a и b имеют один и тот же остаток при делении на m.

Доказательство. ). Пусть a ´ b (mod m) и a = xm + q для некоторых целых x; q таких, что 0 · q < m, то есть q остаток при делении a на m. Тогда a ¡ b = ym влечет b = a ¡ ym = (x ¡ y)m + q. Поскольку 0 · q < m, то q является остатком при делении b на m.

(. Пусть 0 · q < m общий остаток при делении a и b на m. Тогда a = xm + q и b = ym + q для некоторых x; y 2 Z. Вычитая, получаем a ¡ b = m(x ¡ y), следовательно

¹

Поскольку все классы 0; : : : ; m ¡ 1 различны (проверьте это!), то мы получаем следующее

Следствие 31. Число различных классов вычетов по модулю m равно m.

¹

Последнее множество обозначается через Zm. Итак, Zm = f0; : : : ; m ¡ 1g. Например, Z3 =

¹ ¹ ¹ ¹ ¹

f0; 1; 2g, где 0 = 3Z (все целые числа делящиеся на три), 1 = 3Z + 1 (целые числа, дающие

¹

в остатке 1 при делении на 3) и 2 = 3Z + 2.

8

Определение 32. Полная система вычетов по модулю m это любой набор целых чисел n0; : : : nm¡1 такой, что после некоторой перенумерации n0 2 0, n1 2 1, . . . , nm¡1 2 m ¡ 1.

Например, 3; 7; 11 полная система вычетов по модулю 3.

Предложение 33. Пусть a1; : : : ; am полная система вычетов по модулю m. Если k взаимно просто с m, то ka1; : : : ; kam также полная система вычетов по модулю m.

Доказательство. Можно считать, что ai 2 i, следовательно ai ´ i (mod m).

Рассмотрим отображение f из множества f1; 2; : : : ; m ¡ 1g в себя, где f(i) это остаток при делении ki на m. Докажем, что f вложение.

Если f(i) = f(j), то kai ´ kaj (mod m). Поскольку k и m взаимно просты, то мы получаем ai ´ aj (mod m). Тогда из ai ´ i (mod m) вытекает i ´ j (mod m), следовательно i = j.

Но вложение конечного множества в себя является наложением, что и дает нужный результат. ¤

3.2. Решение систем линейных сравнений. Пусть a и b целые числа и m 2 N.

Упражнение 34. Найти все целые решения уравнения

7

Заметим сначала, что, как правило, сравнение (1) имеет бесконечно много решений.

Лемма 35. Если x0 решение сравнения (1), то любой элемент y 2 x0 также является решением этого сравнения.

Доказательство. Из y 2 x0 получаем y = x0 + mz для некоторого z 2 Z. Тогда ay = ax0 + amz ´ ax0 ´ b (mod m). ¤

В общем случае все решения совпадают с некоторым классом вычетов, но, возможно, по другому модулю.

Теорема 36. 1) Если d = НОД(a; m) не делит b, то сравнение (1) не имеет решения.

2) Если d делит b, то это сравнение имеет единственное решение по модулю m1 = m=d (т.е. состоит из элементов одного класса вычетов по модулю m1).

Доказательство. 1) Из ax0 ´ b (mod m) получаем ax0 ¡ b = my для некоторого целого y. Но d = НОД(a; m) делит a и m, следовательно делит b, противоречие.

2) Поскольку d делит a; m и b, то a1 = a=d, m1 = m=b и b1 = b=d целые числа. Нетрудно проверить (сделайте это!), что сравнение (1) эквивалентно сравнению

7По сути речь идет о нахождении целых решений линейного уравнения ax + my = b. Такие уравнения называют диофантовыми, по имени греческого математика Диофанта Александрийского. Общий алгоритм решения линейных диофантовых уравнений был известен и математикам Индии.

9

Докажем сначала, что (2) имеет хотя бы одно решение. Поскольку (a1; m1) = 1, то найдутся целые u; v такие, что a1u + m1v = 1. Домножая это равенство на b1 получаем a1ub1 + m1vb1 = b1. Поскольку m1vb1 делится на m1, то x0 = ub1 решений сравнения (2).

Осталось доказать, что, если y другое решение сравнения (2), то y 2 x0. Действительно из a1y ´ b1 (mod m1) и a1x0 ´ b1 (mod m1) заключаем, что a1(y ¡ x0) делится на m1. Поскольку (a1; m1) = 1, из этого следует m1 j y ¡ x0, что и требовалось. ¤

Например, сравнение 2x ´ 3 (mod 4) не имеет решения, поскольку НОД(2; 4) = 2 не делит 3.

Решим теперь сравнение 6x ´ 4 (mod 10). Сокращая все на НОД(6; 10) = 2, переходим к сравнению 3x ´ 2 (mod 5). Нетрудно видеть, что x0 = 2 решение нашего сравнения. Тогда общее решение является классом вычетов 2 + 5Z = f: : : ; ¡3; 2; 7; : : : g.

3.3. Функция Эйлера. Пусть n ¸ 2 натуральное число. Определим функцию Эйлера '(n) как количество чисел · n взаимно простых с n. Например '(4) = 2, поскольку только 1 и 3 взаимно просты с 4 (а 2 и 4 нет). Аналогично '(6) = 2 и '(9) = 6 (выпишите шесть нужных чисел!). Нетрудно видеть, что если p проcтое число, то '(p) = p ¡ 1.

Нам потребуется следующее простое утверждение.

Лемма 37. В любой полной системе вычетов по модулю m содержится ровно '(m) чисел взаимно простых с m.

Доказательство. Достаточно вспомнить, что НОД(a; m) = НОД(a + mk; m) для любого целого k (завершите доказательство леммы самостоятельно!). ¤

4. Лекция 4

L4

Напомним, что функция Эйлера '(n) определяется как количество натуральных чисел · n взаимно простых с n. Поскольку любое число меньшее простого числа p взаимно просто с ним, то '(p) = p ¡ 1.

Замечание 38. Пусть p простое число. Тогда '(pn) = pn ¡ pn¡1.

Доказательство. Все числа не превосходящие pn и имеющие с ним общие множители исчерпываются списком p; 2p; 3p; : : : ; pn = pn¡1 ¢ p, и их количество равно pn¡1. Оставшиеся

Лемма 39. Число d взаимно просто с произведением ab если и только если (d; a) = 1 и (d; b) = 1 (то есть d взаимно просто с обоими сомножителями a, b).

Доказательство. ). Если z делит d и a, то z делит d и ab, поэтому z = 1. Аналогично показывается, что (d; b) = 1.

(. Предположим, что z > 1 делит d и ab. Разлагая z на множители, можно предполагать, что z = p просто. Тогда из p j ab вытекает либо p j a, либо p j b, скажем первое. Но тогда p > 1 делит d и a, противоречие. ¤

10