Сравнения и теория делимости в системах счисления

1. Введение

Признаки делимости чисел занимают важное место в элементарной и высшей арифметике. Они представляют собой правила, позволяющие установить кратность целого числа заданному делителю без выполнения непосредственной операции деления. Первые систематические сведения о признаках делимости встречаются уже в трудах античных математиков, в частности в работах Евклида, где исследуются свойства делимости целых чисел. В средневековой и новоевропейской математике признаки делимости получили дальнейшее развитие в рамках арифметики натуральных чисел. Классические признаки делимости на 2, 3, 5, 9 и 11 прочно вошли в школьный курс математики благодаря своей простоте и наглядности.
Практическая полезность признаков делимости заключается прежде всего в возможности быстрого анализа числовых данных. Даже в условиях современного вычислительного оборудования они сохраняют значение как средство предварительной оценки, упрощения вычислений и проверки корректности результатов. Кроме того, методы, лежащие в основе признаков делимости, активно применяются в информатике, в частности в алгоритмах контроля ошибок, криптографических протоколах и системах кодирования информации.
С теоретической точки зрения признаки делимости представляют интерес как частный случай более общей теории сравнений по модулю. Современная модульная арифметика позволяет рассматривать делимость чисел в рамках единого формального аппарата, что даёт возможность строго обосновать известные признаки и вывести новые. Особую роль в этом процессе играет позиционное представление чисел в различных системах счисления, так как именно свойства основания системы определяют вид соответствующих признаков делимости.
Несмотря на широкую известность классических признаков, их вывод зачастую остаётся на интуитивном уровне. Это приводит к фрагментарному восприятию материала и не позволяет увидеть общую закономерность. В связи с этим актуальной является задача обобщения признаков делимости и построения универсального метода их получения для произвольного делителя и произвольной системы счисления.
Целью данной работы является формирование строгого подхода к признакам делимости на основе теории сравнений по модулю. В рамках работы предполагается доказать классические признаки делимости средствами модульной арифметики, разработать общий алгоритм построения признаков делимости для произвольного числа и основания системы счисления, а также применить данный алгоритм к выводу и доказательству новых признаков делимости.

Список литературы

1. Виноградов И. М. Основы теории чисел: учеб. пособие для вузов. — М. : Наука, 1981. — 256 с.
2. Бухштаб А. А. Теория чисел : учеб. пособие. — М. : Просвещение, 1972. — 384 с.
3. Кнут Д. Э. Искусство программирования. Том 2. Полу-численные алгоритмы / пер. с англ. — М. : Вильямс, 2016. — 832 с.
4. Серпинский В. Элементарная теория чисел / пер. с польск. — М. : Наука, 1977. — 328 с.
5. Шарыгин И. Ф. Задачи по теории чисел : учеб. пособие. — М. : МЦНМО, 2010. — 256 с.
6. Нивен И., Цукерман Г., Монтгомери Х. Введение в теорию чисел / пер. с англ. — М. : МЦНМО, 2013. — 384 с.
7. Грэхем Р., Кнут Д., Паташник О. Конкретная математика. Основание информатики / пер. с англ. — М. : Вильямс, 2015. — 672 с.
8. Бахвалов Н. С., Жидков Н. П., Кобельков Г. М.
Численные методы : учеб. пособие для вузов. — М. : БИНОМ, 2019. — 640 с.