Связь НОД (а, Ь) и НОК (а, Ь). Задачи на теорию делимости целых чисел

Теорема 2.33

Для любых натуральных а и b верно, что

НОД (а, Ь) ? НОК (а, Ь) = а • b (2.48)

Приведем насколько примеров решения различных задач на теорию делимости целых чисел:

1) /7усть цифры двухзначного числа поменяли местами и из полученного числа вычли исходное. Докажем, что эта разность делится на 9.

Решение. Пусть ab - исходное

ab — ba = (10Ь 4-а) — (10а + Ь) =

= 10Ь + а — 10а- b = 9Ь + 9а = 9(а + Ь) • 9.

2) Докажем, что если к произвольному двухзначному числу приписать двухзначное число, записанное теми же цифрами, но в обратном порядке, то полученное четырехзначное число будет делиться на 11.

Решение. Пусть ab - произвольное число. По условию составляем abba; abba = а ? 10³ + b ? 10² + b ? 10 + а = а ? (10³ + 1) + b ? (10² + 1) =

= 1001а + 110Ь = 11(91а + 10Ь) : 11.

3) Докажем, что число 49¹⁰⁰ - 14⁵⁰ кратно 5.

Решение.

• 1) 49¹⁰⁰ = (49²)⁵⁰ = (24О1)⁵⁰ , следовательно, оканчивается на 1.
• 2) 14⁵⁰ = (14²)²⁵ = (196)²⁵ , следовательно, оканчивается цифрой 6.
• 3) 49¹⁰⁰—14⁵⁰ , следовательно, оканчивается цифрой 5 (...6 - ...1 = ...5)

Поскольку число 49¹⁰⁰ —14⁵⁰ заканчивается цифрой 5, то по признаку делимости, оно кратно пяти.

4) Найдем наибольшее четырехзначное число, все цифры которого различны и которое делится на 2, 5, 9 и 11.

Решение.

• а) Если число делится на 5, то оно заканчивается на 0 или 5; на 2, то оно четное или ноль, следовательно, число должно оканчиваться на 0.
• б) Заметим, что заданные делители, т.е. числа 2, 5,9, 11 взаимно простые, то есть

НОД(2, 5, 9, 11)= 1

Следовательно,

НОК (2, 5, 9, 11) = 2 • 5 ? 9 ? 11 = 990

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

• в) Рассмотрим число 9900. Оно кратно числам 2, 5, 9, 11, но необходимо, что бы все 4 цифры искомого числа были различными. Для этого будем вычитать число 990 из 9900 и искать подходящее.
• 9900-990 = 8910

Число 8910 самое большое из возможных чисел, удовлетворяющих всем условиям.

Ответ: 8910.

5) 77усть одно из двух восьмизначных чисел получено из второго циклической перестановкой вправо. Докажем, что их сумма делится на 11.

Решение: Пусть

х = а_га₂а₃а₄а₅а₆а₇а₈, тогда второе число будет

у = а₈а₁а₂а₃а₄а₅а₆а₇

Пусть

Z ⁼ Cl^CL₂Cl₃Cl₄(l₈CL₈Cl₇.

Тогда

x = 10z + a^, у = z + 10000000

Запишем сумму

х + у = llz + о^(1 + 10000000) = llz + 10000001

Делится на 11 Делится на 11

Следовательно, х + у : 11.