Задачи на делимость

Признаки делимости натуральных чисел известные уже с 6 класса, например, признаки делимости на 2, на 3, на 5, на 9, на 10.
Мы знаем теоремы:
Теорема 1. Если каждое слагаемое суммы делится на одно и то же число, то и сумма делится на это число.
Теорема 2. Если уменьшаемое и вычитаемое делятся на одно и то же число, то и разность делится на это число.
Теорема 3. Если в произведении нескольких натуральных чисел хотя бы один из сомножителей делится на какое-то число, то и все произведение делится на это число.
Теорема 4. Если некоторое целое число делится на другое, а это другое – на третье, то и первое число делится на третье.

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

Формулировка других признаков делимости чисел
Основываясь на известных нам признаках делимости и теоремах 1- 4, можно сформулировать и признаки делимости на 4, на 6, на 8, на 15.
В дополнительной литературе я отыскал признаки делимости на 7, 11, 13, 19, 31, 137, Но для решения очень многих задач на делимость этого оказалось недостаточно. Просматривая учебники математики разных авторов, собрал достаточно большую коллекцию интересующих меня задач.

Признаки делимости чисел можно классифицировать следующим образом:
Делимость по последним цифрам числа
Делимость по сумме цифр числа
Делимость составных чисел

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

Первый метод.
Разложение на множители
(или слагаемые)
Задача 1
Доказать, что n3+3n2+5n+3 делится на 3 при любом натуральном n.
Решение:
представим наш многочлен в виде суммы двух слагаемых:
n3+3n2+5n+3=n3+3n2+2n+3n+3=n(n2+3n+2)+3(n+1)=n(n+1)(n+2)++3(n+1), первое слагаемое есть произведение трех последовательных натуральных чисел, одно из которых обязательно делится на 3, а второе слагаемое содержит множитель 3, => оно делится на 3, а значит и вся сумма делится на 3.

Второй метод.
Исключение целой части числа
Задача 2
Найти все целые x и y, удовлетворяющих уравнению x+y=xy.
Решение:
x+y=xy, <=> x-xy = -y,
x(1-y) = -y,
x = -y/(1-y)
x=y/(y-1)=(y-1+1)/(y-1)=1+(1/(y-1))
(1/(y-1)) є Z, если y-1=±1
y-1=1, y=2
y-1=-1, y=0
Если y=0, то x=0/(1-0)=0
Если y=2, то х=-2/(1-2)=2
Ответ: (0;0) и (2;2).
Последняя цифра числа
Задача 3
Какой остаток при делении на 5 дает число 33333?
Решение:
33333=33332+1 – число оканчивается цифрой 3, остаток от деления на 5 есть 3.

Третий метод. Равноостаточные классы
Задача 4
Доказать, что разность между квадратом числа, которое не делится на 3, и единицей, делится на 3.
Решение:
Если число не делится на 3, то оно имеет вид 3k+1 или 3k+2. В первом случае разность между его квадратом и единицей равна (3k+1)2-1=9k2+6k+1-1=9k2+6k, во втором (3k+2)2-
- 1=9k2+12k+4-1=9k2+12k+3. В обоих случаях разность делится на 3, т.к. каждое слагаемое делится на 3.

Четвертый метод.
Применение теоремы Безу
Задача 5.
Доказать, что выражение 35n-2*5n+11n делится на 6 при любом натуральном n.
Решение:
Запишем наше выражение в таком виде: 35n -
- 2*5n+11n=(35n-5n)+(11n-5n), тогда 35n - 5n делится на разность оснований степеней, т.е. на 35 - 5=30, а следовательно, делится и на 6, 11n -
-5n также делится на разность оснований 11-5=6.

Пятый метод.
Четность и нечетность чисел
Задача 6.
Доказать, что уравнение x2+1974=y2 не имеет решений в целых числах.
Решение:
Предположим, что уравнение имеет решения в целых числах. Запишем данное уравнение в таком виде: 1974=y2-x2. Так как 1974 четное число, то, чтобы уравнение имело решение, необходимо, чтобы разность y2-x2 была четным числом, а это возможно только тогда, когда x и у числа одинаковой четности, т.е. x и у одновременно четные, или оба нечетные числа.
1974=y2-x2 , <=> 1974=(у - х)(у + х). Правая часть делится на 4, а левая – нет, значит, целых решений уравнение не имеет.

Признаки делимости используются при решении уравнений в целых числах (диофантовы уравнения).
Пример 7. Шестой метод.
Найти все целочисленные решения уравнения 16х+20у=14.
Решение: Находим наибольший общий делитель 16 и 20; (16,20) = 4, а число 14 не делится на 4, то по теореме уравнение не имеет целочисленных решений.

Седьмой метод.
Бином Ньютона
Задача8.
Доказать, что 62n+3n+2+3n делится на 11 при всех натуральных n.
Решение:
62n+3n(9+1)=36n+10*3n=(33+3)n+10*3n. Все члены разложения бинома, кроме последнего, имеют множителем число 33, следовательно, делятся на 11. Последний член разложения – 3n. Тогда данное число можно записать так: 36n+10*3n=33A+11*3n, где А – частное от деления n первых членов разложения бинома Ньютона на 33. Но если каждое слагаемое делится на 11, то и сумма делится на 11.

Выводы: Зная методы исследований признаков делимости натуральных чисел можно сформулировать признаки делимости любых натуральных чисел.
Чем особенна и ценна теория чисел? Ведь найти непосредственное применение результатам трудно. Тем не менее, задачи теории чисел привлекают как пытливых молодых людей, так и ученых в течение многих столетий. В чем же здесь дело? Прежде всего, эти задачи очень интересны и красивы. Во все времена человека поражало, что на простые вопросы о числах так трудно найти ответ. Поиски этих ответов часто приводили к открытиям, значение которых далеко превосходит рамки теории чисел