Все мы в школе изучали признаки делимости. Они часто здорово помогают при счете. А вы никогда не задумывались над кем, как их получили впервые?
И возможна ли общая формула, которая бы генерировала признаки делимости на любые числа, какие нам только захочется?))
Заинтригованы? Давайте попытаемся разобраться!
Отталкиваемся от частного
Вспомним признак делимости на 3
Натуральное число делится на 3 тогда и только тогда, когда сумма его цифр делится на 3 (в десятичной записи числа *)
Давайте представим это так:
И заметим очевидный факт: чем левее цифра, тем она весомее.
Когда же мы хотим применить признак делимости на 3, мы просто складываем все цифры:
То есть каждый цифра дает одинаковый вклад.
Теперь время строить аналогии) Посмотрите на картинку записи числа в десятичной системе счисления, каждую цифру там мы домножали на 10 в какой-то степени. А тут каждую цифру получается ни на что не домножаем. То есть домножаем на 1 в какой-то степени!)
Скажем, что мы находимся в 1-ной системе счисления))
Почему так просто с 3?
Легко заметить, что признак делимости такой хороший, так как мы записываем числа в 10-ной системе счисления.
Продолжаем поиск волшебной формулы
Пока мы работаем с числами, записанными в 10-ной системе счисления, вряд ли получится придумать такой же красивый признак для 7, например, потому что 10 - 1 не делится на 7.
А если попробовать рассмотреть выражение 10x - 1?) При каком наименьшем натуральном x оно разделится на 7?
Заметим, что это x = 5. Куда же деть эту найденную 5?)
Мы говорили, что с признаком деления на 3 мы наше число записываем в системе счисления с основанием 1. А может 5 и есть то самое основание нужной системы счисления???
Давайте тестировать нашу гипотезу
Возьмем любое число, делящееся на 7. Пусть это будет 28, например. Распишем его в системе счисления с основанием 5:
Не получилось!( Что делать теперь?? Неужели ничего не получится...
Безумная идея
А с чего мы взяли, что надо прям записывать число как надо? А давайте попробуем перед разложением его просто перевернуть! То есть сделаем самую весомую цифру последнюю, а не первую)
Кажется, получилось! Но может это случайность?
Проверим признак делимости на 19
- Сначала ищем наименьший x, такой что 10x - 1 делится на 19. Это x = 2.
- Теперь выбираем число для тестирования: 1254 (делится на 19)
- Теперь переворачиваем наше выбранное число: 4521
- Записываем его в 2-ной системе счисления:
И опять все получилось! Кажется, мы наконец-то нашли ту самую закономерность!
Общая закономерность
Пусть мы ищем признак делимости на q. Затем мы нашли тот самый минимальный x, что 10x-1 делится на q.
Рассмотрим произвольное число:
Перевернем его:
И запишем в системе счисления с основанием x:
Теперь собственно утверждение, которое мы хотим доказать:
Натуральное число a делится на q тогда и только тогда, когда число a* делится на q
Доказательство
Подсчитаем разность R:
По выбору числа x полученная разность делится на q. Значит, делятся на q и следующие разности:
Следовательно, число R тоже делится на q.
Заметим также, что
Поэтому, если a делится на q, то и a* делится на q!
Аналогично, разность S делится на q:
А теперь заметим, что
А значит, если число a* делится на q, то и a тоже!
Что и требовалось доказать!)
Уточнение
В доказательство мы нигде не воспользовались положительностью числа x, а значит его можно выбирать и отрицательным!
И вообще лучше брать его наименьшим по модулю
Например, для q = 7 можно выбрать не x = 5, а x = -2. Согласитесь, считать будет значительно проще!)
А всегда ли это работает?
Вполне логичный вопрос. Давайте подумаем, где может что-то ломаться. Тогда приходит на ум следующий вопрос:
а всегда ли существует такое x, что 10x - 1 делится на q?
Оказывается, что такой x существует в случае, когда 10 и q взаимно просты!)
Задание для вас!)
Попробуйте каждый придумать свой признак делимости. И расскажите в комментариях! Да так, чтобы ни с кем не повторялось)