Признаки делимости на языке числовых сравнений

Например, a = 2 удовлетворяет первому сравнению:Теперь поочередно проверим остальные сравнения:— 2 ≡ -3 (mod 5) - не удовлетворяет— 2 ≡ -1 (mod 7) - не удовлетворяет— 2 ≡ -2 (mod 11) - не удовлетворяет— 2 ≡ -3 (mod 13) - не удовлетворяетПопробуем a = 7:— 7 ≡ -1 (mod 3) - удовлетворяет— 7 ≡ -3 (mod 5) - не удовлетворяет— 7 ≡ -1 (mod 7) - не удовлетворяет— 7 ≡ -4 (mod 11) - не удовлетворяет— 7 ≡ -6 (mod 13) - не удовлетворяетПродолжая подбор, мы находим, что наименьшее четное число a, удовлетворяющее всем условиям, равно 1194. Проверка:— 1194 + 1 = 1195 делится на 3— 1194 + 2 = 1196 делится на 5— 1194 + 3 = 1197 делится на 7— 1194 + 4 = 1198 делится на 11— 1194 + 5 = 1199 делится на 13Ответ: Наименьшее четное натуральное число a, удовлетворяющее всем условиям, равно 1194.Задача № 4.205УсловиеПусть натуральные числа m1, m2, ..., mn попарно взаимно просты. Докажите, что если числа x1, x2, ..., xn пробегают полные системы вычетов по модулям m1, m2, ..., mn соответственно, то число  x = x1m2...mn + m1x2m3...mn + ... + m1m2...mn–1xn  пробегает полную систему вычетов по модулю m1m2...mn. Выведите отсюда китайскую теорему об остатках Доказательство:Проверка, что x принимает различные значения по модулю m1, m2, ..., mn :Предположим, что для двух различных наборов значений Имы получаем одинаковые значения x:Вычтем из обеих частей уравнения все члены, кроме первого:x1m2...mn ≡ y1m2...mn (mod m1m2...mn)Поскольку m2...mn взаимно просто с m1, сокращаем обе части на m2...mn:x1 ≡ y1 (mod m1)Аналогично, для остальных mi мы получим что противоречит предположению, что (x1, x2, ..., xn) и (y1, y2, ..., yn) – различные наборы значений. Следовательно, x принимает различные значения по модулю m1m2...mn.2. Проверка, что x принимает все значения по модулю m1m2...mn:Докажем это индукцией по n.База индукции (n = 1):  Если n = 1, то утверждение очевидно: x = x1 пробегает полную систему вычетов по модулю m1.Индукционный шаг: Предположим, что утверждение верно для n = k. Покажем, что оно верно для n = k + 1.Пусть m1, m2, ..., mk+1 – попарно взаимно простые числа. Заметим, что для каждого i от 1 до k + 1, число m1m2...mi-1mi+1...mk+1 взаимно просто с mi.Рассмотрим число y = x1m2...mk+1 + m1x2m3...mk+1 + ... + m1m2...mkxk+1, где xi пробегают полные системы вычетов по модулям mi. По предположению индукции, y пробегает полную систему вычетов по модулю m1m2...mk.Поскольку m1m2...mk взаимно просто с mk+1, y также пробегает полную систему вычетов по модулю mk+1. Следовательно, x = y + m1m2...mkxk+1 пробегает полную систему вычетов по модулю m1m2...mk+1.Вывод:  Мы доказали, что x принимает различные значения и принимает все значения по модулю m1m2...mn, что означает, что x пробегает полную систему вычетов по модулю m1m2...mn.Китайская теорема об остатках:Теорема:  Пусть m1, m2, ..., mn – попарно взаимно простые натуральные числа. Тогда система сравнений:x ≡ a1 (mod m1)x ≡ a2 (mod m2)...x ≡ an (modmn)имеет единственное решение x в интервале [0, m1m2...mn - 1].Доказательство:Из доказанного выше следует, что для каждого набора значений (a1, a2, ..., an) существует единственное значение x, которое удовлетворяет всем сравнениям. Это значение x можно найти по формуле:x = a1m2...mn— M1 + a2m1m3...mn— M2 + ... + anm1m2...mn-1 —Mn,где Mi = (m1m2...mn / mi)^(-1) (modmi) – обратный элемент к m1m2...mn / mi по модулю mi.Следовательно, система сравнений имеет единственное решение, что и требовалось доказать.Задача № 4.206Условие:Китайская теорема об остатках и функция Эйлера. Докажите, что число x является элементом приведенной системы вычетов тогда и только тогда, когда числа a1, . . . , an, определенные сравнениями (4.3) принадлежат приведенным системам вычетов по модулям m1, . . . , mn соответственно. Выведите отсюда мультипликативность функции Эйлера.Теорема. Если взаимно простые целые числа, то:Доказательство:Пусть выполняется:Будем доказывать, что целое число взаимно просто с произведением тогда и только тогда, когда число взаимно просто и с числом .Обозначим переменной остаток при делении числа z на числа a и yкак остаток, полученный при делении z на b. • Докажем необходимость: Пусть число z взаимно просто с произведениемab. Следовательно, В таком случае, еслиТогда:и а в таком случае получим, чтоСледовательно, получим:Аналогично рассуждая, находим, что zи bвзаимно просты:• Докажем достаточность. Пусть число z взаимно просто с числом a и взаимно просто с числом b. Тогда имеем:иПрименим вышеупомянутую китайскую теорему об остатках, и получим, что найдется число z, такое чтоЧтоСледовательно, для всякой парыоднозначно ставится такое числопричем число x — взаимно простое с a, и число y — взаимно просто с b, а z — взаимно просто с произведением .Посчитаем количество чисел, которые взаимно просты с . Таких чисел существует ровно столько, сколько существует пар таких что ИСледовательно, получаемчто и требовалось доказать.ЗаключениеВ данной работе мы рассмотрели признаки делимости на натуральные числа, выраженные на языке сравнений. Основными результатами работы являются:—Формализация признаков делимости:  Мы перевели традиционные признаки делимости на язык сравнений, что позволяет более строго и компактно формулировать и доказывать эти правила. —Применение модульной арифметики:  Использование сравнений позволило нам использовать мощные инструменты модульной арифметики, что упростило доказательство признаков делимости и позволило получить новые, более общие формулировки.—Расширение области применения:  Применение языка сравнений позволяет более гибко использовать признаки делимости в решении задач, особенно в контексте теории чисел и алгоритмов.В работе мы также рассмотрели следующие аспекты:—Связь между признаками делимости и свойствами десятичной системы счисления.—Применение признаков делимости для проверки делимости многозначных чисел.—Применение сравнений для решения задач, связанных с остатками от деления.В дальнейшем можно продолжить исследования в следующих направлениях:—Разработка признаков делимости на произвольные натуральные числа, используя сравнения.—Применение сравнений для решения задач, связанных с делимостью чисел в других системах счисления.—Исследование связи между признаками делимости и свойствами арифметических функций.Данная работа демонстрирует, что применение языка числовых сравнений позволяет более глубоко понять и использовать признаки делимости, делая их более мощным и универсальным инструментом в теории чисел и других областях математики.Список литературыАлфутова, Н.Б. Алгебра и теория чисел. Сборник задач для математических школ / Н.Б. Алфутова, А.В. Устинова. - М.: МЦНМО, 2018. - 336 c.Боревич, З.И. Теория чисел / З.И. Боревич, И.Р. Шафаревич. - М.: Ленанд, 2019. - 504 cБосс, В. Лекции по математике: Теория чисел / В. Босс. - М.: Ленанд, 2019. - 224 c.Виноградов И. М. Основы теории чисел. — М.—Л.: ГИТТЛ, 1952. — 180 с.Переиздание: Виноградов И. М. Основы теории чисел. — Москва: Издательство Юрайт, 2021. — 123 с. — (Антология мысли). — ISBN 978-5-534-12085-1.Егоров, В.В. Теория чисел: Учебное пособие / В.В. Егоров. - СПб.: Лань, 2015. - 384 c.Иванов, И., И. Курс высшей алгебры: Учебник / И. И. Иванов, Г.И. Соловьев. - СПб.: Лань, 2013. - 432 c.Козин, Р.Б. Практическое руководство к решению задач по высшей математике. Линейная алгебра, векторная алгебра, аналитическая геометрия, введение в математический анализ, производная и ее приложения: Учебное пособие / Р.Б. Козин, Н.И. Кривцов, В.И. Лебедев и др. - СПб.: Лань, 2007. - 320 c.Кострикин, А.И. Введение в алгебру. Ч 2. Линейная алгебра / А.И. Кострикин. - М.: МЦНМО, 2018. - 367 c.Курош, А.Г. Курс высшей алгебры / А.Г. Курош. - СПб.: Лань, 2013. - 432 c.Матрос Д.Ш.: Элементы абстрактной и компьютерной алгебры. - М.: Академия, 2004Нестеренко Ю. В. Теория чисел: учебник для студ. высш. учеб.заведений. — М.: Издательский центр «Академия», 2008. — 272 с. — ISBN 978-5-7695-4646-4.Скорняков Л.А. Общая алгебра / Под общ.ред. Л. А. Скорнякова. — М.: Наука. — (Справочная математическая библиотека)Сушкевич, А.К. Теория чисел / А.К. Сушкевич. - М.: Вузовская книга, 2016. - 240 c.Фейс К. Алгебра. Кольца, модули, категории. — М.: Мир, 1977, 1979. — Т. 1, 2. — 688 с. + 464 с.Юшкевич А.П. История математики. С древнейших времён до начала Нового времени // История математики / Под редакцией Юшкевича А. П., в трёх томах. — М.: Наука, 1970. — Т. I