Лекция 12: Графы - 2 (стр. 18 )

Наибольшим общим делителем (НОД) двух чисел называется наибольшее натуральное число, на которое делятся они оба. Например, НОД(2,3)=1, НОД(12,18)=6, НОД(1,n)=1, НОД(n, n)=n, НОД(0,n)=n (для любого натурального n). НОД(0,0) не определен. Для краткости часто вместо НОД(a, b) пишется просто (a, b).
(!) Если a и b взаимно просты, то НОД(a, b)=1, что и поясняет смысл обозначения (a, b)=1.
Основное свойство: НОД 2-х чисел - это произведение всех простых множителей этих чисел, каждый из которых взят в минимальной из степеней вхождения в эти числа (т. е. vp((a, b))=min(vp(a),vp(b)) для любого простого p). Действительно, пусть d - любой общий делитель. Т. к. d|a, то vp(d)<=vp(a), т. к. d|b, то vp(d)<=vp(b). Отсюда vp(d)<=min(vp(a),vp(b)). Понятно, что общий делитель будет наибольшим, если эти неравенства превратятся в равенства (и тогда он еще остается делителем). Значит, НОД 2-х чисел - это именно то, что утверждалось в формулировке свойства ч. т.д.
Следствие: НОД 2-х чисел делится на любой общий делитель этих чисел. Действительно, для любого общего делителя d чисел a и b верно неравенство vp(d)<=min(vp(a),vp(b))=vp((a, b)) при всех p. Значит, этот делитель явлется делителем НОД, ч. т.д.

Наименьшим общим кратным (НОК) двух чисел называется наименьшее натуральное число, которое делятся на их оба. Например, НОК(2,3)=6, НОД(12,18)=36, НОК(1,n)=n, НОК(n, n)=n, НОК(0,n) не определен (для любого натурального n). Для краткости часто вместо НОК(a, b) пишется просто [a, b].
(!) Если a и b взаимно просты, то НОК(a, b)=ab. Это можно понять многими способами. Например, согласно св-ву 2 взаимной простоты, любое общее кратное a и b будет делиться на ab, поэтому никакое число, меньшее ab, общим кратным не будет, а само ab - конечно, будет.
Основное свойство: НОК 2-х чисел - это произведение всех простых множителей этих чисел, каждый из которых взят в максимальной из степеней вхождения в эти числа (т. е., vp([a, b])=min(vp(a),vp(b)). Действительно, пусть k - любое общее кратное. Т. к. a|k, то vp(a)<=vp(k), т. к. b|k, то vp(b)<=vp(k). Отсюда vp(k)>=max(vp(a),vp(b)). Понятно, что общее кратное будет наибольшим, если эти неравенства превратятся в равенства (и тогда оно еще остается кратным). Значит, НОК 2-х чисел - это именно то, что утверждалось в формулировке свойства ч. т.д.
Следствие: любое общее кратное 2-х чисел делится на НОК этих чисел. Действительно, для любого общего кратного k чисел a и b верно неравенство vp(k)>=max(vp(a),vp(b))=vp([a, b]) при всех p. Значит, это кратное делится на НОК, ч. т.д.

Примеры:

Задача 1. 8a=13b. Докажите, что a+b-составное число (a и b - натуральные).
Решение: Заметим, что числа 8 и 13 взаимно просты. Тогда, поскольку 13|8a, то 13|a (свойство 3 взаимно простых чисел). Аналогично, поскольку 8|13b, то 8|b. Тогда существуют k и l - частные от этих делений такие, что a=13k, b=8l. Перепишем равенство в виде 8*13k=13*8l, т. е. 104k=104l. Отсюда k=l и b=8k. А тогда a+b=13k+8k=21k. Поскольку 21 - составное число, то 21k составное при любом натуральном k ч. т.д.

(!) Очень ценное соображение: всегда, если xa=yb и x и y взаимно просты, то y|a и x|b.

Задача 2. Докажите, что НОК(a, b)*НОД(a, b)=ab для любых натуральных a и b.
Решение: Докажем это равенство стандартным для задач по теории чисел путем: проверим равенство vp((a, b)*[a, b])=vp(ab) при любом p. Мы уже знаем, что vp(ab)=vp(a)+vp(b), а vp((a, b)*[a, b])=vp((a, b))+vp([a, b])=min(vp(a),vp(b))+max(vp(a),vp(b)). Осталось заметить, что сумма минимума и максимума из двух чисел всегда равна сумме этих чисел... и доказательство готово.

Для тех, кто так и не понял последнего перехода: пусть k и l - два числа (даже не обязательно целых). Пусть, например, k - большее из них (k>=l). Тогда max(k, l)=k, min(k, l)=l и min(k, l)+max(k, l)=l+k=k+l.

Задача 3. Докажите, что произведение любых трех последовательных натуральных чисел делится на 6.
Решение: Среди трех последовательных чисел есть хотя бы одно четное (если наименьшее - нечетное, то четным обязательно будет среднее), поэтому их произведение делится на 2. Кроме того, среди этих чисел обязательно есть хотя бы одно, делящееся на 3 (обозначим наименьшее число за n; если n на 3 не делится, то оно либо дает при делении на 3 остаток 1, и n+2 - наибольшее число - делится на 3, либо остаток 2, и n+1 - среднее число - делится на 3), поэтому их произведение делится на 3. Поскольку 2 и 3 взаимно просты, то произведение 3-х последовательных чисел делится на 2*3=6.

Алгоритм Евклида. Еще древнегреческий математик Евклид изобрел способ нахождения НОД больших чисел, не зная их разложения на простые множители. Его основная идея: если r - остаток отделения a на b, то НОД(a, b)=НОД(b, r). Действительно, a=bq+r, откуда НОД(a, b)|r. Понятно, что НОД(a, b)|b, и поэтому НОД(a, b)|НОД(b, r). Аналогично и НОД(b, r)|НОД(a, b). Значит, НОД(a, b)=НОД(b, r), ч. т.д. Гениальная идея Евклида состоит в том, что можно делить так много раз подряд: каждый раз делитель от предыдущего деления будем делить с остатком на остаток от предыдущего деления. Поскольку числа все время уменьшаются, то за конечное число шагов (не больше величины исходных чисел) мы получим нулевой остаток. Тогда предыдущий остаток d перед ним и будет равен НОД. Действительно, НОД(a, b)=НОД(b, r)=...=НОД(d,0)=d ч. т.д.

Примеры:

Задача 1. Найти НОД(1381955,690713).
Решение: Будем делить с остатком по алгоритму Евклида. 1381955=2*690713+529, откуда НОД(1381955,690713)=НОД(690713,529). Теперь 690713=1305*529+368, откуда НОД(690713,529)=НОД(529,368). Далее, 529=368+161, откуда НОД(529,368)=НОД(368,161). Делим еще раз: 368=2*161+46, откуда НОД(368,161)=НОД(161,46). И еще раз: 161=3*46+23, откуда НОД(161,46)=НОД(46,23). Наконец, 46=2*23 - остаток 0, значит НОД был равен предыдущему остатку, т. е. 23. Для сравнения: разложение на простые даст нам 1381955=5*23*61*197, 690713=23*59*509 - и его нахождение представляет собой долгое упражнение с калькулятором!

Задача 2. Доказать, что дробь (2n+13)/(n+7) несократима.
Решение: Будем находить НОД числителя и знаменателя по алгоритму Евклида. Как ни странно, это помогает и для выражений, содержащих неизвестные. 2n+13=(n+7)+(n+6), откуда НОД(2n+13,n+7)=НОД(n+7,n+6). Теперь n+7=(n+6)+1, откуда НОД(n+7,n+6)=НОД(n+6,1)=1. Ответ будет 1, вне зависимости от значения n. Таким образом, числитель и знаменатель всегда взаимно просты, что и означает несократимость дроби.

Арифметика остатков и определение сравнения. Также одна из самых распространенных идей в олимпиадной теории чисел - это то, что называется "вычисления в кольце вычетов". Проще говоря, вместо того, чтобы складывать, вычитать и умножать числа, можно проводить те же операциис остатками от их деления на какое-либо число - и результат будет давать тот же остаток от деления на это число, что и результат исходных вычислений. Более того, все промежуточные результаты, если они становятся большими, можно заменять на их остатки от деления. Наконец, мы не обязаны заменять именно на остатки - можно брать любые числа, которые дают те же остатки. Главное при этом:
- не применять это к операции деления (а если совсем необходимо, то искать частное по определению: это такое число, которое, будучи умноженным - по модулю - на делитель, дает делимое);
- не менять модуль, по которому производится вычисление, т. е. на разных этапах одного и того же вычисления брать остатки от деления на одно и то жечисло.

Определение: Назовем 2 целых числа a и b сравнимыми по модулю n, если их разность делится на n, или, что то же самое, остатки от деления этих чисел на n одинаковы. (Мы будем записывать это как a=b (mod n), хотя чаще ставится знак тождественного равенства).

(!) Утверждение "n дает остаток r от деления на d" кратко записывается как n=r (mod d).

1. Сумма двух любых целых чисел и сумма чисел, сравнимых с ними по модулю n, сравнимы по модулю n.
Действительно, пусть a=b (mod n), c=d (mod n) - такие же обозначения будут и в следующих пунктах. Тогда, по определению сравнимости, n|a-b и n|c-d. Легко заметить, что сумма двух чисел, делящихся на n, делится на n, то есть n|(a-b)+(c-d)=(a+c)-(b+d). Но это ровно и означает, что a+c=b+d (mod n) ч. т.д.

2. Разность двух любых целых чисел и разность чисел, сравнимых с ними по модулю n, сравнимы по модулю n.
Доказывается точно так же, как предыдущее: только не сумма, а разность двух чисел, делящихся на n, тоже делится на n, поэтому n|(a-b)-(c-d)=(a-c)-(b-d).

3. Произведение двух любых целых чисел и произведение чисел, сравнимых с ними по модулю n, сравнимы по модулю n.
Здесь несколько посложнее: из a=b (mod n) и c=d (mod n) т. е. n|a-b и n|c-d надо вывести ac=bd (mod n), т. е. n|ac-bd. Делаем такой трюк: ac-bd=ac-ad+ad-bd=a(c-d)+(a-b)d. Из n|a-b следует n|(a-b)d, а из n|c-d - n|a(c-d). И из этих двух уже получаем n|a(c-d)+(a-b)d ч. т.д.

Примеры:

Задача 1. Доказать, что n3+2n делится на 3 при любом натуральном n.
Решение: Переберем все возможные остатки n от деления на 3 (перебор всех остатков действительно является полным решением!). Если n=0 (mod 3), т. е. n делится на 3, то n3 и 2n делятся на 3, откуда n3+2n делится на 3. Если n=1 (mod 3), то n3+2n=13+2*1=1+2=3=0 (mod 3), т. е. делится на 3. Если же n=2 (mod 3), то n3+2n=23+2*2=8+4=12=0 (mod 3) - тоже делится на 3. Значит, при любом n (поскольку любое n дает от деления на 3 остаток 0, 1 или 2) n3+2n делится на 3 ч. т.д.

Задача 2. Решить в целых числах: X3-Y3=17.
Решение: Воспользуемся тождеством: X3-Y3=(X-Y)(X2+XY+Y2). Оба множителя в правой части - целые при целых X и Y, а их произведение равно 17, поэтому они будут делителями числа 17. Поскольку это число простое, то нам надо рассмотреть только 4 случая:
1.) X-Y=1, X2+XY+Y2=17. Подставим во второе уравнение Y+1 вместо X: (Y+1)2+(Y+1)Y+Y2=17, то есть 3Y2+3Y+1=17 или 3(Y2+Y)=16. Но 16 не делится на 3, откуда следует отсутствие целых решений в этом случае.
2.) X-Y=17, X2+XY+Y2=1. Подставим во второе уравнение Y+17 вместо X: (Y+17)2+(Y+17)Y+Y2=1, то есть 3Y2+3*17Y+289=1, или 3(Y2+17Y)+288=0. Сократив на 3, получим Y2+17Y+96=0 - квадратное уравнение с дискриминантом 172-4*96=289-384<0. Решений у этого уравнения нет вообще, даже нецелых.
3.) X-Y=-1, X2+XY+Y2=-17.
4.) X-Y=-17, X2+XY+Y2=-1. Случаи отрицательных делителей тоже всегда надо рассматривать. В данном случае (даже в двух) нам просто повезло: выражение X2+XY+Y2 вообще не может быть отрицательным, откуда следует отсутствие решений. Действительно, если XY>=0, то X2+XY+Y2>=X2+Y2>=0, а если XY<=0, то X2+XY+Y2>=X2+2XY+Y2=(X+Y)2>=0 ч. т.д.