Если числа делятся на число, то и любая их линейная комбинация с целыми коэффициентами делится на, т.е. число

Делится на при любых целых.

 

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

Решение: 1-й способ (по алгоритму Евклида).

Поэтому НОД (5040, 2700) = 180.

2-й способ (по разложению на простые сомножители).

Поэтому НОД (5040, 2700) = = 180.

Ответ: 180

 

Пример 6. Найти наибольший общий делитель чисел a = 2²⁰⁰⁵ + 1 и

b = 2²⁰⁰⁶ – 1.

Решение: Пользуясь алгоритмом Евклида, выпишем в ряд числа, имеющие общий делитель. 2²⁰⁰⁶ – 1, 2²⁰⁰⁵ + 1, (2²⁰⁰⁶ – 1)-(2²⁰⁰⁵ + 1)= , . Таким образом, НОД (a,b) = 3.

Ответ: НОД (a,b) = 3.

 

Пример 7. (Задание С6 ЕГЭ 2010). Найдите наибольший общий делитель всех чисел вида р² - 1, где р — простое число, большее 3, но меньшее 2010.

Решение: При . Покажем, что при всех простых число делится на 24.Среди трех подряд идущих чисел одно обязательно делится на 3 и это не , значит . Среди двух подряд идущих четных чисел одно обязательно делится на 4, а другое на 2, значит их произведение делится на 8. Следовательно, число делится на 24. Это и есть наибольший общий делитель, т.к. это наименьшее из наших чисел и все они делятся на 24.

Ответ: 24.

 

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

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

Таким образом, НОД = 11.

Ответ: 11.

Пример 9. Доказать, что дробь несократима.

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

Таким образом, НОД = 1 и дробь несократима.

Пример 10. Найти все целые , при которых - целое число.

Решение: Выделим целую часть дроби и выясним, при каких дробь будет по модулю меньше 1 и не равна 0, т.е. не может быть целым числом. Решив систему неравенств , получим или ,

 

Т.о., дробь может быть целым числом лишь при . Подставляя эти числа в дробь, выделяем решения:

Ответ:

 

Целая и дробная части числа.

Целой частью числа называется наибольшее целое число, не превосходящее данное число. Обозначается Т.е., если, то.

Дробной частью числа называется число . Очевидно,

.

Например,

Пример 11. Решите в натуральных числах уравнение , где – целая часть числа r.

 

Решение: Искомые числа не могут быть чётными, так как при должно выполняться равенство , что невозможно, так как . Пусть теперь n –нечётно, . Тогда . Итак, . Отсюда получаем, что k = 1, 2 или 3. Так что n = 1, 3 или 5. Непосредственной проверкой убеждаемся, что они все подходят.

Ответ: n = 1, 3 или 5.

Пример 12. Докажите, что если делится на , то делится на . (Здесь – целая часть числа r).

Решение: Пусть , тогда . Так как , то а) или б) . Непосредственной проверкой убеждаемся, что в случае а) в случае б) т.о. произведение делится на