10 Класс «Целочисленность и делимость»

Основная теорема арифметики. Всякое натуральное число единственным образом раскладывается в произведение степеней простых чисел: . (Простым называется число, которое не имеет других делителей, кроме 1 и самого себя).

Теорема 1. Количество делителей числа , включая 1 и само число, равно .

Пример 1. (Задание С6 ЕГЭ 2010). Найдите все натуральные числа, последняя десятичная цифра ко­торых 0 и которые имеют ровно 15 различных натуральных дели­телей (включая единицу и само число).

Решение: Ищем числа вида . Воспользуемся теоремой 1 . Из этой теоремы следует, что число различных делителей числа 10 равно 4. Если в разложении числа на простые множители появится еще 1 сомножитель, кроме 2 и 5, то число делителей будет кратным 4, но число 15 (как количество делителей) не делится на 4. Поэтому других делителей нет, т.е. число , а количество делителей равно . Отсюда или 2) Тогда искомыми будут числа: 1) и

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

Если при делении числа на число получается остаток , то , где или

Сравнение чисел по модулю

Определение. Говорят, что число равно числу по модулю :

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

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

Теорема 2. Если то

Пример 2. На какую цифру оканчивается разность 9 2009 – 7 2010 ?

Решение: 9 0 оканчивается на 1 , 9 1 оканчивается на 9 , 9 2 снова оканчивается на 1 , и так далее. Так как , то 9 2009 оканчивается на 9 . Далее, 7 0 оканчивается на 1 , 7 1 оканчивается на 7 , 7 2 оканчивается на 9 , 7 3 оканчивается на 3, 7 4 снова оканчивается на 1 , и так далее. А так как , то 7 2010 оканчивается на 9 . Поэтому разность 9 2009 – 7 2010 оканчивается на 0 .

Другое решение: (С использованием Теоремы 2). Определить, на какую цифру оканчивается число, означает – найти остаток при делении этого числа на 10. .

Пример 3. Покажите, что если m и n - целые числа, а m 2 + n 2 делится на 3 , то m и n оба делятся на 3 .

Решение: заметим, что числа , и дают при делении на 3 дают остатки соответственно 0 , 1 и 1 . Поэтому m 2 + n 2 делится на 3 тогда и только тогда, когда m и n оба делятся на 3 .

Пример 4. (Задание С6 ЕГЭ 2010). Решите уравнение

в натуральных числах.

Решение: Одно решение угадывается сразу: Далее, при делении на 4 число 3 дает в остатке (-1), а число 5 дает в остатке 1, следовательно, правая часть равенства при делении на 4 дает в остатке , а правая часть дает в остатке 1. Отсюда следует, что число - четное, т.е. . Тогда уравнение перепишется в виде . Правая часть равенства при делении на 3 дает в остатке 1, а правая часть дает в остатке . Отсюда следует, что число k - четное, т.е. ( p и q теперь больше 1). Уравнение примет вид: . Тогда . Откуда что дает уже угаданное решение. Если же , то система не имеет решений, т.к. в левой части первого уравнения стоит нечетное число, а в правой – четное.

Наибольший общий делитель (НОД ( )).

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

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

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

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

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

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

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

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

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

b = 2 2006 – 1 .

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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