Лекция 2

Тема 1. Теория делимости

1. Наибольший общий делитель двух чисел и алгоритм Евклида.

По свойству 2, Л-1 делимости целых чисел ( ) из делимости целого числа a на целое число b следует делимость на  b. Поэтому при изучении вопроса о делимости целых чисел можно ограничиться лишь делимостью целых положительных чисел. В дальнейшем и будут рассматриваться лишь положительные делители чисел.

Определение 1. Любое целое число, которое делит одновременно числа a, b, . . . , l называется их общим делителем.

Определение 2. Наибольший из общих делителей чисел a, b, . . . , l называется наибольшим общим делителем этих чисел и обозначается символом (a, b, . . . , l), НОД(a, b, . . . , l) или просто НОД.

Определение 3. Если (a, b, . . . , l) = 1, то числа a, b, . . . , l называются взаимно простыми.

Определение 4. Если каждое из чисел a, b, . . . , l является взаимно простым с каждым другим из них, то числа a, b, . . . , l называются попарно простыми.

Очевидно, что числа попарно простые всегда и взаимно простые. В случае двух чисел понятия попарно простые и взаимно простые совпадают.

П р и м е р ы.

Числа 6, 10, 15, из-за того, что (6, 10, 15) = 1  взаимно простые.

Числа 8, 13, 21, из-за того, что (8, 13) = (8, 21) = (13, 21) = 1  попарно простые.

Далее рассмотрим общие делители двух чисел.

Теорема 1. Если число a является кратным числа b, то совокупность общих делителей чисел a и b совпадает с совокупностью делителей одного числа b; в частности .

Д е й с т в и т е л ь н о, всякий общий делитель чисел a и b является делителем одного числа b. Обратно, если a является кратным b, то в соответствии со свойством 4, Л-1 ( [b | а c | b c | a]), каждый делитель числа b является также и делителем числа a, то есть является общим делителем чисел b и a.

Итак, множество общих делителей чисел a и b совпадает с множеством делителей числа b, а потому что наибольший делитель числа, b является само число b, то (a, b) = b.

Теорема 2. Когда числа a, b, q и r связанны соотношением

a = bq + r, (1)

то совокупность общих делителей чисел a и b совпадает с совокупностью общих делителей чисел b и r; в частности (a, b) = (b, r).

Д е й с т в и т е л ь н о, записанное равенство означает, что любой общий делитель чисел a и b в силу свойства делимости 8, Л-1 (если в равенства k + l + + ... + + q + ... + s относительно всех членов, кроме одного, известно, что они кратны b, то и этот один член кратен b), является делителем числа r, а каждый общий делитель чисел b и r по этому же свойству является делителем числа a.

Таким образом, множество общих делителей чисел a и b совпадает с множеством общих делителей чисел b и r и, итак , (a, b) = (b, r).

Перейдем теперь к нахождению наибольшего общего делителя двух чисел.

Еще Евклид¹ в книге VII своих Начал предоставил способ нахождения НОД двух чисел, который известен теперь, как способ последовательного деления, или алгоритм Евклида.

Он состоит в следующем.

Пусть a и b  положительные целые (натуральные) числа и a > b. Если a не делится на b, то по теореме 1, Л-1 (какие бы ни были целые числа a и b, всегда существует единственная пара целых чисел q и r такая, что a = bq + r и 0  r < b)

a = bq + r₁, 0 < r₁ < b.

Если b не делится на r₁, то по этой же теореме

b = r₁q₁ + r₂, 0 < r₂ < r₁.

Если r₁ не делится на r₂, то

r₁ = r₂q₂ + r₃, 0 < r₃< r₂

и т.д.

Этот процесс последовательного деления не может продолжаться бесконечно, так как в противном случае множество натуральных чисел b > r₁> r₂ > .. .> > > ... не будет иметь наименьшего числа, а это противоречит принципу наименьшего числа (в ряде убывающих натуральных чисел меньших b не может содержаться больше чем b положительных). Итак, существует такое n, что делится на . Процесс последовательного деления заканчивается через шагов, и мы получаем систему равенств

a = bq₀ + r₁,

b = r₁q₁ + r₂,

. . . . . . . . . . . . (2)

r_n2 = r_n1q_n1 + r_n,

r_n1 = r_nq_n.

Рассматривая эти равенства сверху вниз, на основе теоремы 2 получаем, что множество общих делителей чисел a и b совпадает с множеством общих делителей чисел b и r₁, множество общих делителей чисел b и r₁ совпадает с множеством общих делителей чисел r₁ и r₂, множество общих делителей чисел r₁ и r₂ совпадает с множеством общих делителей чисел r₂ и r₃ и т.д. В конце концов, можно прийти к заключению, что множество общих делителей чисел a и b совпадает с множеством общих делителей чисел r_n1 и r_n , и дальше, чем теорема 1 (если число a является кратным числа b, то совокупность общих делителей чисел a и b совпадает с совокупностью делителей одного числа b; в частности ) она совпадает с множеством делителей числа r_n. Тогда справедливые и соотношения _.

Итак, доказанная следующая теорема.

Теорема 3. НОД чисел a и b равняется последнему отличному от нуля остатку r_n в алгоритме Евклида.

С изложенного выше следует также справедливость такого утверждения

Теорема 4. Множество общих делителей чисел a и b совпадает с множеством делителей НОД этих чисел.

Из этой теоремы вытекает

Следствие. НОД чисел a и b делится на любой их общий делитель.

П р и м е р. Применим алгоритм Евклида для нахождения наибольшего общего делителя чисел 525 и 231.

Имеем,

525231

4622

231  63 

1893

63 42 

42 1

4221 

422

0

Здесь положительный последний остаток есть r₃ = 21; поэтому (525, 231)= = 21.

Сформулируем теперь несколько теорем, связанных с понятием НОД двух чисел.

Теорема 5. Если натуральные числа a и b умножить на натуральное число m, то их НОД также умножится на число m, то есть.

(am, bm) = (a, b)m.

Д о к а з а т е л ь с т в о. Умножив обе части каждой из равенств (1) на число m, получаем равенства

am = bmq₀ + r₁m,

bm = r₁ mq₁+ r₂m,

r₁m = r₂ mq₂+ r₃m,

. . . . . . . . . . . . . . .

r_n2m = r_n1mq_n1 + r_nm,

r_n1 = r_nmq_n,

то есть мы имеем алгоритм Евклида для чисел am и bm. Поскольку последний отличный от нуля остаток здесь равняется r_nm, то (am, bm) = r_nm = (a, b)m.

Теорема 6. Если натуральные числа a и b разделить на любой их общий делитель , то НОД этих чисел также поделится на , то есть  =  .

Д е й с т в и т е л ь н о, = (a, b).

С другой стороны, по только что доказанной теореме 5

= .

Итак, (a, b) = . Отсюда = .

Из теорем 5 и 6 вытекают очевидные следствия:

Следствие 1. Частные и от деления чисел а и b на их наибольший общий делитель d взаимно простые, то есть = 1.

Следствие 2. Если частные и от деления чисел а и b на их общий делитель d взаимно простые, то d является их наибольшим общим делителем.

Следствие 3. Если (a, b) = 1, то (ac, b) = (c, b).

Д е й с т в и т е л ь н о, (ac, b) делит ac и bc (если (асс, b) делит b, то (ac, b) делит и bc), значит число (ac, b), в силу теоремы 4 (множество общих делителей чисел a и b совпадает с множеством НОД этих чисел), делит и число (ac, bc), которое равняется соответственно теореме 5 (если натуральные числа a и b умножить на натуральное число m, то их НОД также умножиться на число m) числу c, то есть делит с. Но (ac, b) делит и b, поэтому оно делит и (с, b). Обратно, (с, b) делит ac и b, поэтому оно делит и Таким образом, числа (асс, b) и (c, b) взаимно делят одно одного и, итак, они равные между собою.

Следствие 4. Если (a, b) = 1 и ac делится на b, то с делится на b.

Д е й с т в и т е л ь н о, соответственно теореме 1 (если число a является кратным b, то совокупность общих делителей чисел a и b совпадает с совокупностью делителей одного числа b), при ac, которое делится на b, имеем (ac, b) = b, и с следствия 3 (если (a, b) = 1, то (ac, b) = (c, b)) получаем b = (c, b), а этим (теорема 1) и приходится делимость c на b.

Следствие 5. Если число а является взаимно простым из каждым из чисел b и c, то а взаимно простое с произведением bc.

Приведем также утверждение, что характеризуют свойства НОД нескольких чисел.

Пусть а₁, а₂, . . . , a_n1, а_n  любые целые числа, среди которых хотя бы одно отлично от 0. Пусть (а₁, а₂) = d₂, (d₂, а₃) = d₃, . . . , (d_n2, а_n1)= d_n1, (d_n1, а_n) = = d_n. Тогда (а₁, а₂, . . . , а_n) = (((    ((a₁, а₂), а₃), . . .), ). На основе этого факта можно дать другое определение наибольшего общего делителя.

Определения 2. Наибольшим общим делителем чисел а₁, а₂,. . . , а_n называют неотрицательный общий делитель этих чисел, которое делит любой другой их общий делитель.

Теорема 7. Если каждое a₁,a₂,...,a_m взаимно простое с каждым из чисел b₁,b₂,...,b_n, то и произведение a₁a₂a_m взаимно простое с произведением b₁b₂b_n.

Д е й с т в и т е л ь н о, соответственно следствию 3 (Если (a, b) = 1, то )

(a₁a₂a_m, b₁) = (a₂a₃a_m, b₁) = ... = (a_m, b₁) = 1

и дальше, полагая ради краткости a₁a₂a_m = A, точно таким же путем выводим

(b₁b₂b_n, А) = (b₂b₃b_n, А) = (b₃b₄b_n, А) = ... = (b_n, А) = 1.