Наибольший общий делитель и

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

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

Определение 4. Наименьшим общим кратным (НОК) двух чисел называется наименьшее число, делящееся на каждое из них.

Примеры.

1. 33 = 3 ∙ 11

121 = 11²

НОД (33; 121) = 11

НОК (33; 121) = 3 ∙ 11².

2. a = 2³ ∙ 3¹⁰ ∙ 5 ∙ 7²

b = 2⁵ ∙ 3 ∙ 11

НОД (a; b) = 2³ ∙ 3

НОК (a; b) = 2⁵ ∙ 3¹⁰ ∙ 5 ∙ 7² ∙ 11.

3. a = 2⁵ ∙ 3⁶ ∙ 6² ∙ 8 = 2¹⁰ ∙ 3⁸

b = 2 ∙ 3 ∙ 7³ ∙ 15 = 2 ∙ 3² ∙ 5 ∙ 7³

НОД (a; b) = 2 ∙ 3²

НОК (a; b) = 2¹⁰ ∙ 3⁸ ∙ 5 ∙ 7³.

Обратите особое внимание на то, что во всех примерах мы использовали основную теорему арифметики, то есть разложили каждое из данных чисел на произведение простых сомножителей. Без выполнения этого шага нахождение НОД и НОК довольно-таки значительно усложняется.

Отметим также, что, как оказалось, НОД – это ни что иное как общая часть (пересечение) разложений на простые сомножители двух данных чисел, а НОК – объединение этих разложений. Попробуйте устно доказать этот факт.

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

Определение 5. Два числа называются взаимно простыми, если их наибольший общий делитель (НОД) равен 1.

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

 

Деление с остатком

Определение 6. Число a делится на число b с остатком r, если его можно представить в виде:

a = q ∙ b + r,

где q и r – целые числа, причем 0 ≤ |r| < b. Равенство r = 0 в таком представлении равносильно тому, что число a делится на b.

Замечание. Если же мы рассматриваем деление с остатком лишь на множестве натуральных чисел, как было условлено ранее, то можем снять модуль в неравенстве для остатка: 0 ≤ r < b.

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

Ключевой факт. Число a при делении на число b может давать ровно b возможных вариантов остатков. То есть r = 0, 1, 2, …, b – 1.

Имеют место два важнейших утверждения.

Утверждение 1. Сумма любых двух натуральных чисел и сумма их остатков имеют одинаковые остатки при делении на некоторое число.

Утверждение 2. Произведение любых двух натуральных чисел и произведение их остатков имеют одинаковые остатки при делении на некоторое число.

Доказательство. Пусть рассматриваются два натуральных числа n ₁ и n ₂, которые мы делим на число m. Тогда, согласно с определением 6,

n ₁ = q ₁ ∙ m + r ₁

n ₂ = q ₂ ∙ m + r ₂,

где q ₁, q ₂ – целые числа, а r ₁, r ₂ – соответствующие остатки.

Перемножив числа n ₁ и n ₂, получим

n ₁ n ₂ = (q ₁∙ m + r ₁)(q ₂ ∙ m + r ₂) =

= q ₁ q ₂ ∙ m ² + q ₁ r ₂ ∙ m + q ₂ r ₁ ∙ m + r ₁ r ₂ =

= m ∙ (q ₁ q ₂ m + q ₁ r ₂ + q ₂ r ₁) + r ₁ r ₂.

Число m ∙ (q ₁ q ₂ m + q ₁ r ₂ + q ₂ r ₁), очевидно, делится на m. Следовательно, остаток при делении числа n ₁ n ₂ на m, совпадает с остатком при делении числа r ₁ r ₂ на m.

Упражнение. Докажите утверждение 1.

Определение 7. Два числа a и b сравнимы по модулю натурального числа m (или равноостаточны при делении на m), если при делении на m они дают одинаковые остатки. Число m в таком случае называется модулем сравнения.

Обозначение. Если числа a и b сравнимы по модулю натурального числа m, то пишут, что a ≡ b (mod m).

Пример. Числа 32 и 18 сравнимы по модулю 7, поскольку 32 = 7 ∙ 4 + 4 и 18 = 7 ∙ 2 + 4. То есть 18 ≡ 32 (mod 7).

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

Задача 1. Произведение двух натуральных чисел, каждое из которых не делится нацело на 10, равно 1000. Найдите их сумму.

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

Решение задачи 1. Поскольку произведение двух натуральных чисел равно 1000 = 2³ ∙ 5³, то каждое из чисел в своем разложении может содержать лишь двойки и пятерки. Заметим, что оба этих множителя не могут присутствовать в разложении одного числа, иначе оно будет делиться на 10. Следовательно, одно из чисел равно 5³, а другое – 2³. Тогда их сумма равна 5³ + 2³ = 125 + 8 = 133.

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

Теперь давайте вспомним о том, что такое наибольший общий делитель (НОД) и наименьшее общее кратное (НОК). Имеет место следующее важнейшее утверждение.

Утверждение. Для любых натуральных чисел a и b выполняется равенство:

НОД (a, b) ∙ НОК (a, b) = ab.

Доказательство. Пусть НОД (a, b) = m. Тогда, согласно с введенным нами в предыдущей лекции определением наибольшего общего делителя, имеют место равенства:

a = a ₁ m,

b = b ₁ m,

где числа a ₁ и b ₁ взаимно просты – НОД (a ₁, b ₁) = 1.

Тогда из определения наименьшего общего кратного следует, что НОК (a, b) = a ₁ b ₁ m.

Следовательно, НОД (a, b) ∙ НОК (a, b) = m ∙ a ₁ b ₁ m = a ₁ m ∙ b ₁ m = ab.

Ключевой момент. При решении задач на НОД и НОК бывает полезно обозначить НОД двух чисел некоторой неизвестной, а затем выразить эти числа и их НОК через эту неизвестную.

В доказательстве утверждения мы обозначили НОД чисел a и b некоторой неизвестной m, а затем выразили a, b и их НОК через эту неизвестную m.

Не бойтесь вводить неизвестные! Впоследствии от них всегда можно избавиться, если окажется, что они каким-либо образом выражаются через другие введенные ранее неизвестные либо же (что тоже бывает) косвенным образом известны из условия задачи.

Рассмотрим еще один пример применения подобных рассуждений.

Задача 2 (окружной этап Всероссийской математической олимпиады): Натуральные числа a и b таковы, что НОД (a, b) + НОК (a, b) = a + b.

Докажите, что одно из чисел a или b делится на другое.

Решение. Пусть НОД (a, b) = m. Тогда a = a ₁ m, b = b ₁ m, где НОД (a ₁, b ₁) = 1. Тогда НОК (a, b) = a ₁ b ₁ m. По условию НОД (a, b) + НОК (a, b) = a + b. Преобразуем данное уравнение в соответствии с введенными нами обозначениями.

m + a ₁ b ₁ m = a ₁ m + b ₁ m;

m (1 + a ₁ b ₁) = m (a ₁ + b ₁).

Поскольку m – число, не меньшее единицы, то можем сократить на него обе части уравнения.

1 + a ₁ b ₁ = a ₁ + b ₁;

1 + a ₁ b ₁ – a ₁ – b ₁ = 0;

(1 – a ₁) – b ₁(1 – a ₁) = 0;

(1 – a ₁)(1 – b ₁) = 0.

Следовательно, хотя бы одно из чисел a ₁ и b ₁ равно единице. В случае, если a ₁ = 1, a = m и тогда b, очевидно, делится на a (из определения). В случае, если b ₁ = 1, получаем b = m и, следовательно, a делится на b.

 

Признаки делимости

Определение 1. Признак делимости – это правило, позволяющее быстро определить, является ли число кратным заранее заданному числу, без необходимости выполнять деление непосредственно.

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

 

Признак Паскаля

Блез Паскаль – один из знаменитейших людей в истории человечества. Прожив всего 39 лет, он вошел в историю как известнейший французский математик, физик, литератор и философ. Паскаль стал одним из основателей математического анализа, теории вероятностей и проективной геометрии, создателем первых образцов счетной техники, а также автором основного закона гидростатики.

Паскаль не обошел своим вниманием и классическую арифметику: он нашел общий алгоритм построения признаков делимости любого целого числа на любое другое целое число, который и называют признаком Паскаля.

Признак Паскаля – это метод, позволяющий получить признаки делимости на любое число, своего рода «универсальный признак делимости». Приступим к его описанию на примере натуральных чисел и десятичной системы счисления.

Признак Паскаля:

Пусть дано натуральное число k, которое записывается в десятичной системе счисления как , где a ₀ – единицы, a ₁ – десятки и так далее.

Пусть m – некоторое произвольное натуральное число, на которое мы хотим делить и, соответственно, выводить признак делимости на него.

Найдем ряд остатков по следующей схеме:

r ₁ – остаток от деления числа 10 на число m;

r ₂ – остаток от деления числа 10 ∙ r ₁ на число m;

r ₃ – остаток от деления числа 10 ∙ r ₂ на число m;

…

r_n – остаток от деления числа 10 ∙ r_{n – 1} на число m.

Формально этот ряд остатков можно задать так:

r ₁ ≡ 10 (mod m);

r_i ≡ 10 ∙ r_{i –1} (mod m), i = 2, 3, …, n.

Поскольку возможных остатков при делении на m конечное число, то этот процесс зациклится, причем не позже, чем через m шагов, и дальше его можно не продолжать.

Процесс зациклится, начиная с некоторого i = i ₀: r_{i + p} = r_i, где p – получившийся период последовательности остатков { r_i } (количество шагов до начала повторов). Для единообразия можно принять, что r ₀ = 1.

Тогда число k дает при делении на m тот же остаток, что и число

r_n ∙ a_n + … + r ₂ ∙ a ₂ + r ₁ ∙ a ₁ + a ₀.

Посмотрим же теперь, как работает этот алгоритм на примере нескольких частных случаев. Рассмотрим примеры построения признака делимости по методу Паскаля.

Пример 1 (признак делимости на 2).

Строим ряд остатков по методу Паскаля:

r ₀ = 1;

r ₁ ≡ 10 (mod 2) = 0;

r ₂ ≡ 10 ∙ 0 (mod 2) = 0;

…

r­_n ≡ 0.

Согласно с признаком Паскаля, число дает при делении на 2 такой же остаток, как и число 0 ∙ a_n + … + 0 ∙ a ₂ + 0 ∙ a ₁ + a ₀ = a ₀.

Отсюда получаем известный признак: остаток от деления числа на 2 равен остатку от деления его последней цифры на 2, или, проще говоря, число делится на 2, если его последняя цифра четна.

Пример 2 (признаки делимости на 3 и 9).

Здесь берем m = 3 или m = 9. Поскольку остаток от деления 10 как на 3, так и на 9, равен 1, то все r_i = 1 (i = 0, 1, 2, …, n).

Значит, остаток от деления числа на 3 (или на 9) равен остатку от деления суммы его цифр на 3 (соответственно, 9), или, проще говоря, число делится на 3 (или 9), если сумма его цифр делится на 3 (или 9).

 

Пример 3 (признак делимости на 7).

Здесь m = 7. Строим ряд остатков по методу Паскаля:

r ₀ = 1;

r ₁ ≡ 10 (mod 7) = 3;

r ₂ ≡ 10 ∙ 3 (mod 7) = 30 (mod 7) = (4 ∙ 7 + 2) (mod 7) = 2;

r ₃ ≡ 10 ∙ 2 (mod 7) = 20 (mod 7) = (2 ∙ 7 + 6) (mod 7) = 6;

r ₄ ≡ 10 ∙ 6 (mod 7) = 60 (mod 7) = (8 ∙ 7 + 4) (mod 7) = 4;

r ₅ ≡ 10 ∙ 4 (mod 7) = 40 (mod 7) = (5 ∙ 7 + 5) (mod 7) = 5;

r ₆ ≡ 10 ∙ 5 (mod 7) = 50 (mod 7) = (7 ∙ 7 + 1) (mod 7) = 1.

r ₆ = 1 = r ₀ – цикл замкнулся.

Следовательно, для любого числа его остаток от деления на 7 совпадает с остатком от деления на 7 числа a ₀ + 3 a ₁ + 2 a ₂ + 6 a ₃ + 4 a ₄ + 5 a ₅+ a ₆ + ….

В качестве примера рассмотрим число 48916. Согласно с доказанным выше признаком,

48916 ≡ 6 + 3 ∙ 1 + 2 ∙ 9 + 6 ∙ 8 + 4 ∙ 4 = 6 + 3 + 18 + 48 + 16 = 91 ≡ 1 + 3 ∙ 9 = 1 + 27 = 28 ≡ 0 (mod 7). А значит, число 48916 делится на 7.

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

Упражнение. Докажите методом Паскаля признак делимости на 4: число делится на 4, если число, состоящее из 2 его последних цифр, делится на 4.

 

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

На прошлой лекции мы обсудили понятие наибольшего общего делителя двух натуральных чисел и выяснили, как его можно найти: достаточно выписать разложения этих чисел на простые множители и взять их общую часть. Однако для больших чисел эта процедура практически неосуществима. Попробуйте, например, таким способом найти наибольший общий делитель чисел 1381955 и 690713. К счастью, существует другой метод, позволяющий вычислить НОД двух чисел. Он называется алгоритмом Евклида.

Алгоритм Евклида основан на следующем простом соображении: любой общий делитель чисел a и b (a > b) делит также число a – b; кроме того, любой общий делитель чисел b и a – b делит число a. Тем самым, НОД (a, b) = НОД (b, a – b). Мы, по существу, изложили алгоритм Евклида.

Покажем, как он работает для конкретных чисел на следующем примере.

Пример 4. Найдем наибольший общий делитель чисел 451 и 287:

НОД (451, 287) = НОД (287, 164) =

= НОД (164, 123) =

= НОД (123, 41) =

= НОД (82, 41) =

= НОД (41, 41) =

= 41.

Заметим, что алгоритм Евклида можно ускорить: заменять a не на a – b, а сразу на остаток от деления a на b. Продемонстрируем это на примере чисел, приведенных в начале нашей подтемы.

Пример 5. Найдем наибольший общий делитель чисел 1381955 и 690713:

НОД (1381955, 690713) = НОД (690713, 529) =

= НОД (529, 368) =

= НОД (368, 161) =

= НОД (161, 46) =

= НОД (46, 23) =

= НОД (23, 0) =

= 23.

Как видно, этот метод очень быстро приводит к результату.

Задача 3. Найти наибольший общий делитель чисел 2 n + 13 и n + 7 (n ϵ N).

Решение. НОД (2 n + 13, n + 7) = НОД (n + 7, n + 6) = НОД (n + 6, 1) = 1.

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

Задача 1 (Районная олимпиада 2010, 7 класс). Возможно ли подобрать 2010 целых чисел, произведение которых равно 2, а сумма равна нулю?

Решение. Для того, чтобы получить в произведении 2010 целых чисел двойку, среди этих чисел должно быть ровно одно число ±2, а остальные 2009 чисел – это ±1. Но теперь ясно, что сумма подобного набора чисел всегда нечетна, поскольку в нее входят одно четное число и 2009 нечетных. Поскольку ноль – четное число, то отсюда и следует, что подобрать такие 2010 целых чисел невозможно.

Как видим, при использовании уже известных нам приемов при решении задач на четность, задачка районной олимпиады оказалась вполне решабельной. Обратим внимание на еще одну задачку районной олимпиады, похожую по условию на предыдущую.

Задача 2 (Районная олимпиада 2010, 8 класс). Возможно ли подобрать 2010 целых чисел, произведение которых равно 4, а сумма равна нулю?

Решение. Для того, чтобы получить в произведении 2010 целых чисел четверку, среди этих чисел должно быть либо одно число ±4 (остальные 2009 – это ±1), либо два числа ±2 (остальные 2008 –±1). Вариант с ±4 рассматривать бесполезно из соображений четности (см. Задачу 1). Следовательно, возможным может быть лишь вариант с ±2. Такой вариант уже подобрать несложно. К примеру, такие числа: 1002 числа 1, 1006 чисел –1, а также два числа 2.

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

Подведем промежуточный итог. Использование четности в смысле инварианта нередко помогает решить, на первый взгляд, не очень-то приятные задачи. Кроме того, соображения четности могут быть крайне полезны при решении задач с рассмотрением нескольких вариантов – часть из них могут быть моментально отсеяны.

Теперь же мы вернемся к нашим обычным задачкам. И, в качестве важнейшего утверждения, рассмотрим такую задачу.

Задача 3. Докажите, что простых чисел бесконечно много. (Либо, что то же самое – докажите, что множество простых чисел бесконечно.)

Решение. Доказательство будем проводить уже привычным для нас методом от противного. Предположим, что множество простых чисел конечно. То есть пусть p ₁, p ₂, …, p_n – все простые числа, какие только могут быть. Тогда построим число a = p ₁ p ₂… p_n + 1. Заметим, что при делении на любое простое число, не превышающее его, оно будет давать остаток 1. Следовательно, оно будет делиться лишь на единицу и само себя, что и означает, что построенное нами число a – простое, причем отличное от p ₁, p ₂, …, p_n.

Авторство этому утверждению нередко приписывают Евклиду, одному из величайших математиков древности. Некоторые современные авторы, отдавая дань уважения Евклиду, называют его наблюдение теоремой Евклида.

Раз уж мы вспомнили о Евклиде, грех не вспомнить уже известное нам еще одно его творение – алгоритм Евклида для нахождения НОД двух чисел (см. Лекцию 8).

Задача 4. Докажите, что дробь – несократима ни при каком натуральном n.

Решение. Вспомним, что дробь называют несократимой, если НОД ее числителя и знаменателя равен единице. НОД (30 n + 2, 12 n + 1) = НОД (12 n + 1, 6 n) = НОД (6 n, 1) = 1. Следовательно, данная дробь несократима.

А смогли бы Вы решить эту задачу без алгоритма Евклида? Попробуйте. Далее мы рассмотрим серию базовых задач на делимость.

Задача 5. Докажите, что произведение любых трех последовательных натуральных чисел делится на 6.

Указание. Среди этих трех чисел есть хотя бы одно четное число и одно число, делящееся на 3.

Задача 6. Докажите, что произведение любых пяти последовательных чисел делится а) на 30; б) на 120.

Решение. Среди этих чисел есть число, кратное 3, есть число, кратное 5, и есть два четных числа, одно из которых делится на 4.

Мерцающий кадр (МК)*. 56 a = 65 b. Докажите, что a + b – составное число.

Решение (Денискин Андрей). Поскольку числа 56 и 65 взаимно просты, то из уравнения следует, что a = 65 k, b = 56 k, где k – некоторое целое число. Тогда a + b = 65 k + 56 k = 121 k. Очевидно, что число 121 k для любого k будет составным, поскольку 121 = 11² – составное число.

Задача 7. p – простое число. Сколько существует натуральных чисел, меньших p и взаимно простых с ним?

Решение. Всего натуральных чисел, меньших p – ровно p – 1. Заметим, что все они будут взаимно просты с p, поскольку простое число p имеет всего два делителя – единицу и самого себя (а ни одно из чисел, меньших p, не может на него делиться).

Задача 8. Докажите, что число, имеющее нечетное число делителей – точный квадрат.

Решение. Заметим, что если d – некоторый делитель числа n, то n / d – также делитель n. Таким образом, все делители числа n можно разбить на пары, то есть их число должно быть четно. Но поскольку по условию число имеет нечетное число делителей, то наше разбиение на пары должно где-то нарушиться. А нарушиться оно может лишь в случае, когда делитель d и его «пара» n / d совпадают, то есть d = n / d, откуда n = d ², что и требовалось доказать.