Признаки делимости начинают проходить еще в 5 классе и во общем-то за время обучения в школе ученик узнает признаки делимости на 2, 3, 4, 5, 6, 9, 10 (возможно на 11). Но все эти признаки в десятичной системе счисления, а что если система счисления была бы другой? На сколько просто было бы вывести подобные признаки для n-чной системы?
Очевидное:
Признаки деления на n и на n/2 (если n четное) полностью соответствуют признакам деления на 10 и на 5. Тут все просто и понятно. Признак делимости на 2 при четном n так же очевиден.
Не очевидное:
А как быть с признаком деления на n-1, аналогичен ли он признаку деления на 9? Оказывается, что да. То есть если сумма цифр делится на n-1 то и все число будет делиться на n-1.
Почему так? Попробуем это доказать. (k+1)-значное число в n-ичной системе счисления имеет вид:
Можно заметить, что:
Тогда число a можно представить в виде:
Преобразуем к виду:
Первое слагаемое очевидно делится на n-1, следовательно все число делится на n-1 только если сумма цифр (второе слагаемое) делится на n-1.
Получили признак делимости аналогичный признаку делимости на 9 в десятичной системе счисления. Из него следуют аналогичные признаки делимости на все делители числа n-1.
Например в 16-ричной системе счисления признаки делимости на 3, 5 и 15 имеют вид "Если сумма цифр делится на 3 (5, 15), то само число делится на 3 (5, 15)".
Вот такие признаки делимости. Всем приятных вычислений.