Расин, Алгебра

Д о к а з а т е л ь с т в о. В силу леммы 2 существует такое sZ, что r + s = s + r = 0. Тогда q + s + r = q + 0 = q; стало быть, x = q + s является решением данного уравнения. Перейдем к проверке единственности решения. Пусть x1 + r = q = x2 + r. Тогда

x1 = x1 + 0 = x1 + r + s = x2 + r + s = x2 + 0 = x2.

Решение уравнения x + q = r назывется разностью чисел r и q и обозначается r −q. В частности, число 0 −r выше было названо противоположным к r и обозначено через −r.

Лемма 5. Пусть r, s, t, u – произвольные целые числа. Тогда

(a)−(r + s) = (−r) + (−s),

(b)(r + s) − (t + u) = (r − t) + (s − u).

Д о к а з а т е л ь с т в о. Проверим, что число (−r) + (−s) является противоположным к силу r + s. Используя свойства коммутативности и ассоциативности сложения, получаем

r + s + (−r) + (−s) = r + (−r) + s + (−s) = 0 + 0 = 0.

Поскольку единственность элемента, противоположного данному, уже доказана, мы получили свойство (a).

Чтобы проверить свойство (b), достаточно убедиться в том, что число x = (r−t)+(s−u) является решением уравнения (t+u)+x = = r +s. Из определения разности целых чисел имеем t+(r −t) = r и u + (s − u) = s. Поэтому

(t + u) + (r − t) + (s − u) = (t + (r − t)) + (u + (s − u)) = r + s.

Так как уравнение (t + u) + x = r + s имеет единственное решение, свойство (b) также доказано.

Следующие три утверждения связаны со свойствами операции умножения на множестве Z. Доказательства этих свойств мы опускаем.

Лемма 6. Для произвольного r Z выполнены равенства

(a)r · 1 = 1 · r = r,

(b)r · 0 = 0 · r = 0

40

Лемма 7. Для любых r, s, t Z выполнены равенства

(a)r · s = s · r,

(b)(r · s) · t = r · (s · t).

Лемма 8. Для любых r, s, t Z выполнено равенство

r · (s + t) = r · s + r · t.

Таким образом, кроме операции сложения, на множестве Z определена операция умножения, которая обладает нейтральным элементом 1 (лемма 6), является коммутативной и ассоциативной (лемма 7), и, кроме того, выполняется свойство дистрибутивности (лемма 8). Наличие на множестве Z операций сложения и умножения таких, что относительно сложения Z – абелева группа, а для умножения выполнены перечисленные выше свойства, кратко выражают следующим образом: Z является коммутативным кольцом с единицей.

Лемма 9. Для любых r, s Z выполнены равенства

(a)r · (−s) = (−r) · s = −(r · s),

(b)(−r) · (−s) = r · s.

Д о к а з а т е л ь с т в о. Проверим свойство (a). Используя дистрибутивность, имеем

0 = r · 0 = r · (s + (−s)) = r · s + r · (−s).

Из этого равенства видно, что число r · (−s) является противоположным к числу r·s; это означает, что r·(−s) = −(r·s). Равенство (−r) · s = −(r · s) легко следует из доказанного равенства и коммутативности умножения.

Свойство (b) легко получается из свойства (a). Действительно,

(−r) · (−s) = (−(−r)) · s = r · s.

Здесь мы использовали единственность элемента, противоположного к данному: в самом деле, элемент −(−r), противоположный к −r, в силу единственности совпадает с r.

Следуя сложившейся практике, в дальнейшем знак умножения мы, как правило, будем опускать, т. е. r·s будем записывать в виде rs.

41

3.2. Порядок на множестве Z

Пусть r, s Z. Число r меньше числа s (r < s), если разность s − r является натуральным числом.

Введенное нами отношение “меньше” на множестве Z, как и раньше, называется порядком.

Сформулируем основные свойства порядка на множестве Z.

Предложение 3.1. Пусть r, s, t, u – произвольные целые числа. Тогда

(1)если r < s и s < t, то r < t (транзитивность);

(2)для любых r и s выполнено в точности одно из трех соотношений: либо r = s, либо r < s, либо s < r (линейность);

(3)если r < s и t < u, то r + t < s + u;

(4)если r < s и 0 < t, то rt < st;

(5)если 0 < r < s и 0 < t < u, то rt < su.

(6)если 0 < r < s, то r2 < s2.

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

(2) вытекает из того факта, что разность r − s должна быть либо нулем, либо целым положительным числом, либо целым отрицательным числом.

Проверим свойство (5). Используя дважды свойство (4), имеем rt < st и st < su. Используя свойство (1), получаем требуемое неравенство.

Свойство (6) немедленно вытекает из свойства (5).

Нестрогий порядок определяется стандартно: r 6 s, если r = s или r < s. Читателю полезно сформулировать и доказать аналог предложения 3.1 для нестрогого порядка.

3.3. Абсолютная величина целого числа

Абсолютная величина (модуль) целого числа r равна r, если r > 0, и равна −r, если r < 0.

Как обычно, абсолютная величина r обозначается через |r|.

42

Предложение 3.2. Пусть r и s – произвольные целые числа. Тогда

(1)| − r| = |r|;

(2)|r|2 = r2;

(3)−|r| 6 r 6 |r|;

(4)|rs| = |r||s|;

(5)|r + s| 6 |r| + |s|.

Д о к а з а т е л ь с т в о. Свойства (1)–(3) очевидны. Для проверки свойств (4), (5) воспользуемся следующим легко проверяемым утверждением: если a > 0 и b > 0, то из равенства a2 = b2 следует равенство a = b, а из неравенства a2 6 b2 следует неравенство a 6 b. Это утверждение следует из свойств (2) и (6) порядка на множестве целых чисел (см. разд. 3.2).

Равенство (4) проверяется без труда. В самом деле, достаточно проверить, что |rs|2 = (|r||s|)2. Последнее равенство выполнено, поскольку левая и правая его части равны r2s2.

Докажем неравенство (5). Из неравенства rs 6 |r||s| следует неравенство r2 + 2rs + s2 6 r2 + 2|r||s| + s2. Это неравенство с использованием свойства (2) можно переписать в виде |r + s|2 6 6 (|r|+|s|)2. Поскольку |r+s| и |r|+|s| неотрицательны, получаем требуемое неравенство.

3.4. Теорема о делении с остатком

Пусть m и n – целые числа. Говорят, что n делит m (обозначение n |m), если m = un для некоторого целого u.

Легко понять, что в кольце целых чисел далеко не всегда одно число делит другое. В связи с этим при изучении свойств целых чисел важное значение имеет следующее утверждение, называемое теоремой о делении с остатком.

Теорема 3.1. Пусть m, n – произвольные целые числа, причем n 6= 0. Тогда существуют такие однозначно определенные числа u, r, что m = un + r и 0 6 r < |n|.

Д о к а з а т е л ь с т в о. Проверим, что такие числа u, r всегда найдутся. Предположим сначала, что m и n – натуральные числа.

43

Если m < n, то, очевидно, u = 0, r = m. Столь же просто рассматривается случай, когда n делит m. В этом случае m = un + 0 для некоторого целого u. Поэтому можно считать, что m > n и n не делит m. Рассмотрим множество

R = {s | s N и s = m − vn для некоторого v N}.

Множество R непусто (ему, например, принадлежит число m − −n) и состоит из натуральных чисел. Поэтому в силу теоремы 2.1 множество R имеет наименьший элемент r. Покажем, что r < n. Учитывая, что

для некоторого u Z, из предположения r > n легко получить противоречие. В самом деле, если r = n, то из равенства (1) следует, что m = (u + 1)n; это невозможно, так как n не делит m. Если допустить, что r > n, то r − n – натуральное и r − n = = m − (u + 1)n. Таким образом, r − n R, что противоречит выбору r. Итак, мы нашли числа u, r таким образом, что m = un + r

и 0 < r < n.

Осталось рассмотреть возможность, когда хотя бы одно из чисел m, n не является натуральным. Если m = 0, то u = r = 0. Пусть m < 0 < n. Тогда −m и n – натуральные числа; поэтому −m = u1n + r1, 0 6 r1 < n. Стало быть,

Из равенств (2) видно, что u = −u1, r = 0, если r1 = 0, и u = = −u1 − 1, r = n − r1, если r1 > 0.

Пусть n < 0 < m. Тогда m = u1(−n) + r1, 0 6 r1 < −n. Легко понять, что u = −u1, r = r1.

Предположим, наконец, что m, n < 0. Тогда −m = u1(−n) +

Из равенств (3) видно, что u = u1, r = 0, если r1 = 0, и u = u1 + 1, r = −n − r1, если r1 > 0.

Проверим единственность требуемых чисел. Пусть m = u1n + r1, m = u2n + r2, 0 6 r1, r2 < |n|.

44

Тогда u1n + r1 = u2n + r2, откуда r1 − r2 = (u2 − u1)n. Переходя в этом равенстве к абсолютным величинам, получим

Если предположить, что u1 6= u2, то |u2 − u1| > 1; поэтому |u2 − −u1||n| > |n|. Нетрудно проверить, что из условия 0 6 6 r1, r2 < |n| следует неравенство |r1 − r2| < |n|. Таким образом, предположение u1 6= u2 приводит к противоречию: правая часть равенства (4) не меньше |n|, а левая строго меньше |n|. Стало быть, u1 = u2, а из равенства (4) следует r1 = r2.

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

В 3.4 в кольце Z было определено отношение делимости: n |m, если m = un для некоторого целого u.

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

(D1) m |m;

(D2) если m |n и n |m, то |m| = |n|; (D3) если m |n и n |p, то m |p;

(D4) если m |n и m |p, то m |sn + tp, каковы бы ни были целые

(D6) если m |n, то |m| 6 |n|.

Особо отметим, что m |0, каково бы ни было целое число m; с другой стороны, если 0 |n, то n = 0.

Теперь мы можем обсудить важное для дальнейшего изложения понятие наибольшего общего делителя двух целых чисел.

О п р е д е л е н и е. Число d называется наибольшим общим делителем целых чисел m, n, если выполнены свойства:

(a)d |m и d |n;

(b)если c |m и c |n, то c |d.

Нетрудно видеть, что если d – наибольший общий делитель чисел m, n, то тем же свойством обладает и −d.

45

В дальнейшем неотрицательный наибольший общий делитель чисел m, n будет обозначаться (m, n).

Заметим, что из определения наибольшего общего делителя вытекают равенства (0, n) = (n, 0) = n, если n 6= 0; значение выражения (m, n) при m = n = 0 будем считать неопределенным.

Убедимся теперь, что для любых целых m, n 6= 0 наибольший общий делитель (m, n) существует. Заметив предварительно, что у взаимно противоположных целых чисел множества делителей совпадают, будем считать, что числа m, n являются натуральными.

Рассмотрим множество

Dm,n = {b | b N и b = sm + tn для некоторых s, t Z}.

Множество Dm,n непусто (почему?) и состоит из натуральных чисел; поэтому оно имеет наименьший элемент d.

Справедливо следующее важное утверждение.

Теорема 3.2. Для любых натуральных чисел m, n наименьший элемент d множества Dm,n равен их наибольшему общему делителю (m, n).

Д о к а з а т е л ь с т в о. Проверим сначала, что d является общим делителем чисел m, n. Из того, что m = 1 ·m+ 0 ·n, n = 0 ·m+ 1 ·n, следуют включения m, n Dm,n. Поэтому достаточно проверить, что d делит любое a Dm,n. По теореме о делении с остатком имеем a = ud + r, 0 6 r < d. Стало быть,

Но d, a Dm,n, поэтому d = sm + tn, a = s1m + t1n, где s, t, s1, t1 –

некоторые целые числа. Подставляя выражения для d и a в равенство (5), получим

Из равенства (6) видно, что если r > 0, то r Dm,n. Полученное включение противоречит выбору числа d поскольку r < d. Таким образом, r = 0, т. е. d |a.

46

Пусть теперь c |m и c |n. Так как d = sm + tn, по свойству (D4) получаем, что c |d.

Следствие. Для любых целых чисел m, n найдутся такие целые числа s, t, что (m, n) = sm + tn.

Отметим следующие свойства наибольшего общего делителя.

Предложение 3.3. Пусть m, n – произвольные целые числа. Тогда

(a)(m, n) = (n, m);

(b)((m, n), p) = (m, (n, p));

(c)(mn, mp) = |m|(n, p).

Д о к а з а т е л ь с т в о. Выполнение свойства (a) очевидно. Проверим свойство (b). Пусть d = ((m, n), p). Тогда d делит все три числа m, n, p, и потому делит m, (n, p); стало быть, d общий делитель этих чисел. Пусть теперь c – произвольный общий делитель чисел m, (n, p). Понятно, что c делит все три числа и, следовательно, делит d. Тем самым показано, что d = (m, (n, p)).

Проверку свойства (c) мы оставляем читателю в качестве упражнения.

Замечание. Тот факт, что каждой паре целых чисел ставится в соответствие их наибольший общий делитель, означает, что на Z, кроме операций сложения и умножения, определена еще одна операция – вычисление наибольшего общего делителя. Предложение 3.3 показывает, что эта операция коммутативна и ассоциативна.

Введем важное для дальнейшего изложения понятие взаимно простых чисел.

О п р е д е л е н и е. Целые числа m, n называются взаимно простыми, если (m, n) = 1.

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

Теорема 3.3. Целые числа m, n взаимно просты тогда и только тогда, когда sm + tn = 1 для некоторых целых s, t.

Д о к а з а т е л ь с т в о. Если m, n взаимно просты, то применяя следствие из теоремы 3.2, сразу получаем равенство sm + tn = 1, где s, t – некоторые целые числа

47

Пусть существуют такие целые s, t, что sm + tn = 1. Если d = (m, n), то по свойству (D4) d | sm + tn; стало быть, d | 1. Поскольку d > 0, получаем, что d = 1. Таким образом, m и n взаимно просты.

Взаимно простые числа обладают рядом полезных свойств. Отметим следующие три свойства.

(1)если (m, n) = 1 и (m, p) = 1, то (m, np) = 1;

(2)если m |n, p |n и (m, p) = 1, то mp |n;

(3)если m |np и (m, n) = 1, то m |p.

Доказательство свойств (1) – (3).

Пусть (m, n) = 1 и (m, p) = 1, тогда sm + tn = 1, um + vp = 1

для некоторых целых s, t, u, v. Перемножив эти равенства, получим

(msu + spv + ntu)m + (tv)np = 1.

Так как в скобках стоят целые числа, применение теоремы 3.3 показывает, что числа m и np взаимно просты. Свойство (1) доказано.

Проверим свойство (2). Пусть m |n, p |n и (m, p) = 1. Так как m и p взаимно просты, найдутся такие целые s, t, что sm + tp = 1, откуда

Поскольку m | n, имеем mp | np. Аналогично, из p | n следует, что mp | mn. Таким образом, mp делит правую часть равенства (7); следовательно, делит и его левую часть.

Перейдем к доказательству свойства (3). Пусть m |np и (m, n) = 1. Имеем sm + tn = 1, откуда

Очевидно, m делит правую часть равенства (8), поэтому делит и левую его часть.

48

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

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

Рассмотрим натуральные числа m, n. Положим r1 равным остатку от деления m на n. Если r1 > 0, то пусть r2 – остаток от деления n на r1. Допустим теперь, что числа r1, r2, . . . ri уже найдены и ri > 0. Тогда через ri+1 обозначим остаток от деления ri−1 на ri. Нетрудно понять, что отличные от нуля остатки образуют убывающую последовательность:

r1 > r2 > . . . > ri > ri+1 > . . . .

Обозначим через R множество таких остатков. Множество R состоит из натуральных чисел, поэтому к нему применима теорема 2.1. Таким образом, в R существует наименьший отличный от нуля остаток rk. Остаток от деления rk−1 на rk не может принадлежать множеству R, и потому он равен нулю. Следовательно, rk |rk−1.

Убедимся, что последний отличный от нуля остаток rk является наибольшим общим делителем чисел m и n. Из теоремы о делении с остаком вытекает, что справедливы следующие равенства

где u1, u2, . . . , uk, uk+1 – некоторые целые числа.

Проверим сначала, что rk – общий делитель чисел m и n. Используя тот факт, что rk |rk−1, будем перемещаться по равенствам

1Евклид (365 – ок. 300 до н. э.) – выдающийся древнегреческий математик. Автор всемирно известной книги “Начала”, посвященной аксиоматическому изложению геометрии.

49