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

Класс

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

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

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

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

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

Ответ: и

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

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

, где .

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

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

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

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

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

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

Решение: 9⁰ оканчивается на 1 , 9¹ оканчивается на 9 , 9² снова оканчивается на 1 , и так далее. Так как , то 9²⁰⁰⁹ оканчивается на 9 . Далее, 7⁰ оканчивается на 1 , 7¹ оканчивается на 7 , 7² оканчивается на 9 , 7³ оканчивается на 3, 7⁴ снова оканчивается на 1 , и так далее. А так как , то 7²⁰¹⁰ оканчивается на 9 . Поэтому разность 9²⁰⁰⁹ – 7²⁰¹⁰ оканчивается на 0 .

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

Ответ: на 0.

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

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

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

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

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

Ответ:

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

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