Основные свойства нод

Теорема 1. На всякое число, на которое делятся без остатка два данных числа, делится и их наибольший общий делитель.

Пример. НОД (3540; 450) = 30. Кроме того, данные числа 3540 и 450 имеют общие делители 1. 2, 3, 5, 6, 10, 15.

Очевидно, что на каждый из этих общих делителей делится без остатка НОД чисел 3540 и 450, т. е. число 30.

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

Пример. НОД (3540; 450) = 30. Делителями 30 являются числа: 1. 2, 3, 5, 6, 10, 15. Очевидно, что на каждое из этих чисел делятся 3540 и 450.

Теорема 3. Если каждое из двух данных чисел a и b умножить на какое-либо натуральное число m, то и наибольший общий делитель данных чисел умножится на то же число m.

Пример. НОД (558; 540) = 18. Умножив каждое из данных чисел на 2, будем иметь: НОД ( ) = 36.

Теорема 4. Если каждое из двух данных чисел a и b разделить на один из общих делителей этих чисел, то и их наибольший общий делитель разделится на это число.

Пример. НОД (864; 192) = 96. Разделив каждое из данных чисел 864 и 192 на один из их общих делителей, например на 32, получим:

.

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

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

Пример. Пусть требуется найти НОД чисел 7200 и 8400. Сначала разделим данные числа на 100, от этого НОД чисел 7200 и 8400 уменьшится в 100 раз. Потом найдем НОД частных 72 и 84, который будет равен 12. Наконец, 12 умножим на 100, получим 1200. Значит НОД (7200; 8400) = 1200.

Теорема о частных, полученных от деления данных чисел на их нод

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

Если НОД (a; b; c; …; l) = m, тогда .

Пример. НОД (108; 60) = 12. . Следовательно, 9 и 5 числа взаимно простые числа.

Теорема о делимости произведения двух чисел на число, взаимно простое с одним из сомножителей.

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

Если ab = p; p делится на c, НОД (a; c) = 1, тогда b делится на c.

Пример. . Произведение двух сомножителей делится на 15; один из сомножителей - 7 - взаимно простое с 15, НОД (7; 15) = 1. Следовательно, по теореме, второй сомножитель должен делиться на 15. Действительно, 90 : 15 = 6.

Применение теории делимости к решению неопределенных уравнений в целых числах

Определение. Неопределенные уравнения - уравнения, содержащие более одного неизвестного.

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

Пример 1. Решить в целых числах уравнение , где y и p - простые числа.

Решение

Преобразуем уравнение . Если имеются целые решения этого уравнения, тогда делится на , так как НОД (x³, x² - 1) = 1, но y³ и p являются взаимно простыми числами, т. е. , значит, p не делится на x³, следовательно, y³ делится на x³, что возможно, если x = y, т. е. x - простое число. Тогда , что возможно, если , т. е. x = 2, y = 2, p = 3.

Ответ: x = 2, y = 2, p = 3.

Пример 2. Найти целые решения уравнения .

Решение

Преобразуем уравнение ,

. Произведение целых чисел будет равно 1 в двух случаях, когда каждый из сомножителей равен 1, и когда каждый из сомножителей равен -1.

Получим совокупность двух систем уравнений:

(1) и (2)

Решим каждую систему уравнений: (1) (2)

Ответ:

Пример 3. Найти все целые решения уравнения: , где p - простое число.

Решение

Преобразуем уравнение:

.

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

(1) (2) (3) (4)

В результате решения систем, получаем:

(1) (2) (3) (4)

Ответ:

Пример 4. Найти все целые решения уравнения: .

Решение

Преобразуем уравнение:

.

Произведение двух целых сомножителей равно 18. Чтобы выяснить, каким числам могут быть равны эти сомножители, найдем все делители числа 18:

18 имеет делители: 1, 2, 3, 6, 9, 18. Если первый множитель равен первому из делителей 18, тогда второй множитель будет равен последнему - получим шесть пар решений:

(1) (2) (3)

(4) (5) (6)

(1) (2) (3) (4) (5) (6)

Ответ:

Пример 5. Найти натуральные значения корней уравнения

.

Решение

Преобразуем уравнение: .

Отсюда получаем четыре системы уравнений:

(1) (2) (3) (4)

Поскольку x и y - натуральные числа, находим:

Ответ:

Уравнения вида ax + by = c, где a, b, c - целые числа, отличные от нуля

Теорема 1. Если НОД (a; b) = d, то существуют такие целые числа x и y, что имеет место равенство .

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

Пример. Найти линейное представление наибольшего общего делителя чисел 1232 и 1672.

Решение

1) Применим алгоритм Евклида и найдем НОД(1232, 1672):

НОД(1232, 1672) = 88.

2) Выразим 88 последовательно через неполные частные и остатки, используя полученные равенства, начиная с конца:

, т. е. .

Теорема 2. Если в уравнении ax + by = l (a, b) = 1, то уравнение имеет по крайней мере одно целое решение.

Справедливость этой теоремы следует из теоремы 1. Таким образом, чтобы найти одно целое решение уравнения ах + by = 1, если (а, b) = 1, достаточно представить число 1 в виде линейной комбинации чисел а и b.

Пример. Найти целое решение уравнения 15x + 37y = 1.

Решение

1) Применим алгоритм Евклида и найдем НОД(15, 37):

НОД(15, 37) = 1

2) Выразим 1 последовательно через неполные частные и остатки, используя полученные равенства, начиная с конца:

, т. е.

x₀ = 5, y₀ = -2.

Теорема 3. Если в уравнении ах + by = с (а, b) = d > 1 и с не делится на d, то уравнение целых решений не имеет.

Для доказательства теоремы достаточно предположить противное.

Пример. Найти целое решение уравнения 16x - 34y = 7.

Решение

(16, 34) = 2, 7 не делится на 2, уравнение целых решений не имеет.

Теорема 4. Если в уравнении ах + by = с (a, b) = d > 1 и c делится на d, то оно равносильно уравнению а₁х + b₁у = c₁, в котором (a₁, b₁) = 1.

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

Теорема 5. Если в уравнении ах + by = с (а, b) = 1, то все целые решения этого уравнения заключены в формулах:

где x₀, y₀ - целое решение уравнения ах + by = 1, t - любое целое число.

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

Приведенные теоремы позволяют установить следующее правило решения в целых числах уравнения ах + by = с, где (а, b) = 1:

1) находится целое решение уравнения ах + by = 1 путем представления 1 как линейной комбинации чисел а и b (существуют и другие способы отыскания целых решений этого уравнения, например при использовании цепных дробей);

2) составляется общая формула целых решений данного уравнения:

где x₀, y₀ - целое решение уравнения ах + by = 1, t—любое целое число.

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

Пример 1. Найти целые решения уравнения 407х - 2816у = 33.

Решение

1) Упрощаем данное уравнение, приводя его к виду 37х - 256у = 3.

2) Решаем уравнение 37x - 256y = 1.

.

.

3) Найдем решения данного уравнения по формулам:

Ответ:

Пример 2. Найти наибольшее трехзначное число, которое при делении на 17 дает остаток 9, а при делении на 22 дает остаток 4.

Решение

Пусть частное от деления трехзначного числа на 17 равно x, тогда искомое число равно: 17x + 9, причем . Так как при получаем двузначное число, а при x = 6 - уже трехзначное; при x = 60 получим четырехзначное число, а при x = 59 будет число трехзначное.

Пусть частное от деления трехзначного числа на 22 равно y, тогда искомое число равно: 22y + 4, причем . Этот промежуток устанавливаем аналогично промежутку для значений x.

По условию: 17x + 9 = 22y + 4, 22y - 17x = 5 - это неопределенное уравнение.

1) Решим уравнение: -17x + 22y = 1.

значит,

2) Общий вид всех целых решений данного уравнения:

.

.

Положим , тогда , если t = 1, тогда x = 67, y = 52 - эти значения уже выходят за пределы промежутков и .

Поскольку требуется найти наибольшее трехзначное число, то удовлетворять условию задачи будут значения .

Искомое трехзначное число будет равно:

или .

Ответ: 774.

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

Например, число 840 делится на 120, и на 140; на произведение же , очевидно, число 840 не разделится.

13