XI Международная студенческая научная конференция Студенческий научный форум - 2019

Введение

Заблаговременным условием к формированию теории сравнений стало восстановление сочинений Диофанта, которые были выпущены Баше де Мезириаком, в 1621 году. Изучение сочинений Диофанта привело Ферма́ к открытиям, которые существенно опередили своё время. 18 октября 1640 года он сообщил без доказательства теорему, которая впоследствии получила название малой теоремы Ферма. Первым доказал эту теорему Лейбниц он открыл эту теорему независимо от Ферма́ не позднее 1683 года и сообщил об этом с приведением точного доказательства Бернулли. Позднее исследование проблем, посвященных теории чисел и теории сравнений, было продолжено Эйлером, который внедрил квадратичный закон взаимности и обобщил теорему Ферма.

Понятие и символьное обозначение сравнений было введено Гауссом, как важный инструмент для обоснования его арифметической теории, работа над которой была начата им в 1797 году. В своей книге «Арифметика исследования» (1801) К. Гаусс не только точно определил отношение сравнимости согласно данному модулю, но и систематически развил теорию сравнений – важнейший раздел теории чисел.

Сравнения по модулю и арифметика остатков развивалась в работах таких ученых как Пьер Ферма, Леонард Эйлер, Иоганн Карл Фридрих Гаусс, Блез Паскаль.

Мы считаем тему «Сравнения по модулю и арифметика остатков» актуальной, поскольку сравнения имеют широкое применение в различных областях науки, техники, экономики. Помимо этого, эта тема имеет большое значение, так как она встречается в заданиях повышенной сложности, которые содержатся в дидактических материалах, олимпиадных задачах, заданиях вступительных экзаменов в ВУЗы и на ЕГЭ.

Объект исследования – сравнения по модулю и арифметика остатков в элементарной математике.

Предмет исследования – методы и приемы решения задач на сравнения по модулю и арифметика остатков.

Цель – систематизация теоретического материала по теме «Сравнения по модулю и арифметика остатков» и его применение к решению задач.

Результаты исследования были представлены на конференциях «Молодежь в мире науки» и «Студенчество в научном поиске»( место).

Работа состоит из введения, двух частей и заключения. Список использованной литературы включает наименований.

Глава I. Теоретические сведения о сравнениях и признаках делимости.

Понятие сравнения по модулю

Рассмотрим множество целых чисел и произвольное целое, неравное нулю.

Определение 1. Два целых числа и называются сравнимыми по модулю , если разность этих чисел делится на .

Так как делимость на равносильна делимости на , то можно считать, что .

Если числа и сравнимы по модулю , то пишут . Условие , означает, что делится на . Поэтому числа и сравнимы по модулю в том и только том случае, когда делится на .

Теорема 1. Два целых числа сравнимы по модулю тогда и только тогда, когда имеют одинаковые остатки при делении на

Доказательство. Пусть остатки при делении на равны, то есть

где

Вычтем (2) из (1); получим , то есть или

Обратно, пусть Это означает, что или

Разделим на ; получим Подставив в (3), будем иметь , то есть при делении на получается тот же остаток, что и при делении на .

Иногда целесообразней в решении задач воспользоваться именно определением, а не теоремой. Потому что при использовании теоремы нам надо будет разделить число на , число на , а затем сравнить получившиеся числа. А с помощью определения нам достаточно вычесть из числа число и разделить получившееся вполне конкретное число на . Данное определение облегчает решение, если числа большие, а также при решении можно воспользоваться признаком делимости двух чисел.

Приведем несколько примеров сравнений:

, , .

Отметим далее несколько часто используемых фактов.

1. Если два целых числа и сравнимы по модулю , то это можно записать различными способами: или , (где целое число), или , или .

2. Если , то и или , т.е. всякое число, кратное , сравнимо с нулем по модулю .

3. Если , т.е. при делении на дает остаток , то или .Таким образом, всякое целое число всегда сравнимо с остатком , получающимся при делении его на .

1.2. Свойства сравнений

Остаток и частное при делении на заданное число могут быть получены с помощью алгоритма деления. Однако при больших числах применение алгоритма деления приводит к длинным вычислениям. Во многих случаях может быть значительно проще получить результат, используя свойства сравнений.

В элементарной математике выделяют два вида свойств сравнений:

Свойства сравнений, не зависящие от модуля.

Свойства сравнений, зависящие от модуля.

Рассмотрим свойства сравнений, не зависящие от модуля.

Отношение является отношением эквивалентности, то есть удовлетворяет требованиям:

Рефлексивности:;

Симметричности: если , то и

Транзитивности: если , а , то

2) Сравнения по одному и тому же модулю можно почленно складывать.

3) Два сравнения по одному и тому же модулю можно почленно вычитать одно из другого.

4) К обеим частям сравнения можно прибавлять одно и то же целое число (следствие свойств 1, 2, 3).

Действительно, пусть любое целое число. По свойству рефлексивности , а согласно свойствам 2 и 3 имеем

Следствие 1.Члены сравнения можно переносить из одной части сравнения в другую с противоположным знаком.

5) Сравнения по одному и тому же модулю можно почленно перемножать.

Следствие 2. Обе части сравнения можно возводить в одну и ту же неотрицательную степень: если и целое неотрицательное число, то

6) Обе части сравнения можно умножать на одно и то же целое число.

Рассмотрим, свойства сравнений, зависящие от модуля.

7) Если , то

Доказательство. Так как , то

А так как , то в силу транзитивности отношения делимости , то есть

8) Обе части сравнения и модуль можно умножить на одно и то же целое положительное число.

Действительно, пусть и целое положительное число. Тогда , или .

Если

Доказательство. Пусть

Из следует , или , откуда .Так как

, ,то , или , т.е.

Следствие 3. Если , т.е. если , то из следует , а это означает, что обе части сравнения и модуль можно разделить на любой их общий делитель.

Большое значение имеет следующее следствие.

Следствие 4. Если , т.е. если , , то из следует , а это означает, что обе части сравнения можно разделить на их общий делитель, если он взаимно прост с модулем.

10) Пусть многочлен с целыми коэффициентами, и переменные, принимающие целые значения. Тогда если , то .

Доказательство. Пусть . По условию , тогда при , , ,…,

Умножая обе части каждого из полученных сравнений на , получим: , где , , ,

Складывая последние сравнения, получим: . Если и , , то

Свойство 10 имеет ряд важных применений. В частности, с его помощью можно дать теоретическое обоснование признаков делимости.

Всякое натуральное число можно представить в виде систематического числа: .

Сравнение первой и второй степени

Сравнения первой степени.

Любое сравнение первой степени с неизвестным можно привести к виду:

, где

Если в это сравнение вместо будем подставлять различные целые числа, то будем получать верные или неверные числовые сравнения. Те значения , которые дают верные числовые сравнения, называют решениями сравнения .

Выясним условия, при которых сравнение имеет единственное решение, несколько решений или не имеет ни одного решения.

Теорема 2. Если , то сравнение имеет решение и притом единственное.

Доказательство. Рассмотрим какую-нибудь полную систему вычетов по модулю :

, , …, .

По условию . Тогда согласно алгоритму Евклида совокупность чисел: , , …, или , , …,

тоже полная система вычетов по модулю . Таким образом, если в вместо подставлять последовательно все вычеты полной системы вычетов , то левая часть этого сравнения пробегает все значения полной системы вычетов. Но это означает, что для одного и только для одного число окажется в том же самом классе, к которому принадлежит число ; при этом .

Итак, если , то сравнение имеет и притом единственное решение , или , .

Решение сравнения можно найти путем испытания полной системы абсолютно наименьших вычетов. Для нахождения решения сравнения можно также воспользоваться следующей теоремой.

Теорема 3. Если , то решением сравнения

является класс .

Доказательство. По условию , тогда согласно теореме, Эйлера , откуда , или . Сравнивая последнее сравнение с , находим, что класс является решением сравнения , а согласно теореме это решение единственно.

Пример 1. Решить сравнение .

Так как , то сравнение имеет единственное решение.

; , так как .

Ответ: .

Пример 2. Решите сравнение .

Решение.

1. Заменим коэффициенты сравнения соответствующими наименьшими положительными вычетами по модулю 516, получим:

2. Если наибольший общий делитель чисел и равен и делит , то сравнение имеет решений. Если же не делит , то сравнение не имеет решений. Для сравнения имеем Поскольку делит , то сравнение , а, значит, и сравнение имеет решения.

3. Разделим обе части сравнения и его модуль на , получим:

Рассмотрим два способа решения сравнения , где

Первый способ:

Решение. находим по формуле , где – числитель предпоследней подходящей дроби для числа , разложенного в непрерывную (цепную) дробь. Разложим число в непрерывную дробь и найдем числитель предпоследней подходящей дроби:

Найдем числители подходящих дробей по рекуррентной формуле

, где , , ,...,:

Получим, что , и решение сравнения имеет вид:

Второй способ:

По теореме Эйлера для чисел a и m, которые удовлетворят условию , выполняется сравнение , где функция Эйлера.

Поэтому решение сравнения можно найти по формуле

Найдем . Поскольку , то по свойствам функции Эйлера

Тогда

1. Итак, является решением сравнения . Все решения сравнения , а также сравнения , находят по формуле

, где , ,…,

В нашем случае , , , значит,

Ответ:, , .

Сравнение второй степени.

Теория сравнений связана с решением в целых числах уравнений второй степени с двумя неизвестными.

Любое сравнение второй степени

можно упростить, изменив его коэффициенты и сделав замену переменной.

Умножив обе части сравнения на число , не делящееся на , получим равносильное сравнение

Его можно переписать в виде или

где использованы обозначения и Так как , сравнение

при любом целом имеет единственное решение относительно . Это устанавливает взаимно-однозначное соответствие между решениями сравнения относительно и сравнения относительно .

Из изложенного следует, что в дальнейшем можно рассматривать лишь сравнения вида

Вычисление решения данного уравнения является трудной задачей теории чисел и используется в криптографии с открытыми ключами для построения односторонней функции. Далее рассмотрим алгоритмы вычисления квадратных корней по целочисленному простому модулю.

Для того чтобы узнать, разрешимо ли сравнение, достаточно вычислить символ Лежандра. Если , то сравнение не имеет решения. При сравнение разрешимо и имеет ровно два решения. Действительно, если , то по определению символа Лежандра сравнение имеет хотя бы одно решение . Пусть − другое решение сравнения. Тогда , , то есть . Значит, что хотя бы одно из выражений должно делиться на . В первом случае получаем уже имеющееся решение , во втором случае решение .

При этом значения и различны, в противном случае выполнялось бы соотношение , что невозможно, поскольку НОД НОД .

Рассмотрим некоторые способы решения сравнения

Пусть , то есть , где – целое число. Разрешимость cравнения означает, что . По свойству символа Лежандра имеем . Тогда .

Таким образом, решение имеет вид .

Пример 3. Решим сравнение .

Решение. Вычисляем символ Лежандра: , значит, сравнение разрешимо. Число представляем в виде , то есть .

Находим решение:

Ответ:

Нахождение остатков при делении на данное число

Остаток и частное при делении на данное число можно получить с помощью алгоритма деления. Однако при больших значениях чисел применение алгоритма деления приводит к трудоемким вычислениям. Упростить решение задач и получение результата возможно, если использовать свойства сравнений.

Так как любое целое число можно представить в виде суммы или разности целых чисел, в виде степени или суммы степеней, то достаточно овладеть навыками нахождения остатков от деления суммы, разности, степени, суммы степеней на некоторое число .

Из теории сравнений мы знаем, что целое число и остаток от деления на число принадлежит одному и тому же классу по модулю , т.е. . Остаток является наименьшим неотрицательным вычетом числа по модулю .

Пусть , , остатки от деления чисел , , , на . Тогда:

а) Складывая почленно сравнения получим:

Из следует, что остатки от деления чисел и на равносильны. Следовательно, нахождение остатка от деления числа на можно упростить – нахождением остатка от деления числа на .

Если , то будет искомым остатком. Вычитая, например, второе сравнение из первого почленно, получим: , можно и наоборот, тогда .

б) Умножая почленно сравнения , получим сравнение . Из этого следует такое же утверждение, подобное утверждению из пункта а).

в) Если , то получим: .

Следовательно, нахождение остатка от деления на переходит к нахождению остатка от деления на . Задача становится проще, но при больших значениях и может потребовать достаточно трудоемких вычислений. Рассмотрим наиболее часто используемые приёмы, которые применяют в этом случае.

1) Последовательное возведение в степень сравнения с дальнейшей заменой правой части этого сравнения абсолютно наименьшими вычетами по модулю .

2) Если и взаимнопростые, т.е. , , то можно воспользоваться теоремой Эйлера (в случае теоремой Ферма).

Теорема Эйлера. Для любых , таких что, НОД , выполнимо .

По теореме Эйлера: . Разделим далее на с остатком: . Тогда получим: , и задача нахождения остатка от деления на , таким образом, переходит к нахождению остатка от деления на (где ), что почти не вызывает затруднений.

Признаки делимости

Иногда появляется необходимость, не выполняя самого деления, определить делится ли одно число на другое. Критерий, который устанавливает необходимое и достаточное условие делимости любого натурального числа на натуральное число , называется признаком делимости на .

Есть общие признаки, которые действительны для любого , и частные – для отдельных значений .

Общий признак делимости представляет правило, согласно которому по цифрам числа , записанного в системе счисления с основанием , можно сделать заключение о делимости его на другое число .

Теорема 5 (общий признак делимости Паскаля). Для того чтобы число , которое записано в произвольной ичной системе счисления в виде

, делилось на число , необходимо и достаточно, чтобы число делилось на (здесь цифры числа , а абсолютно наименьшие вычеты соответствующих степеней по модулю , , , , ).

Доказательство. Пусть , где абсолютно наименьший вычет числа по модулю , , , .

Тогда

Число делится на тогда и только тогда, когда

Из сравнений ( ) и ( ) и транзитивности отношения сравнимости (см. ) получаем условие, эквивалентное условию ( ):

Из приведенного выше следует вывод: для того, чтобы делилось на , необходимо и достаточно, чтобы делилось на . Теорема доказана.

В качестве следствий из общего признака Паскаля вытекают различные признаки делимости. Рассмотрим некоторые из них, которые чаще всего используются на практике.

Следствие 5. Пусть делитель числа . Для того чтобы число, записанное в ичной системе счисления, делилось на , необходимо и достаточно, чтобы сумма его цифр делилась на .

Доказательство. В данном случае , а ; тогда , т.е. , а потому: .

Итак, для того чтобы делилось на , необходимо и достаточно, чтобы сумма цифр этого числа делилась на .

Следствие 6. Пусть делитель числа . Чтобы число, которое записано в ичной системе счисления, делилось на , необходимо и достаточно, чтобы разность между суммой цифр на четных и нечетных местах делилась на .

Доказательство. В данном случае , а ; тогда , то есть , а потому . В результате вытекает утверждение следствия.

Для чисел, записанных в десятичной системе счисления, получаем общеизвестный признак делимости на : для того чтобы число делилось на , необходимо и достаточно, чтобы разность между суммой цифр на четных местах и нечетных местах делилась на .

Пример 4.Число делится на 11, так как разность делится на .

Следствие 7. Пусть делитель числа . Для того чтобы число, записанное в ичной системе счисления, делилось на , необходимо и достаточно, чтобы число, записанное последними цифрами данного числа, делилось на .

Доказательство. В данном случае для , а потому

но так как , то

Из вышеперечисленного следует утверждение следствия.

Для чисел, которые записаны в десятичной системе счисления, из следствия вытекает целый ряд частных признаков делимости. Рассмотрим некоторые из них:

1) Основание (здесь ) делится на , , . В этом случае получим признаки делимости на , , .

а) Для делимости числа на необходимо и достаточно, чтобы последняя цифра была четной.

б) Для делимости числа на необходимо и достаточно, чтобы последняя цифра делилась на .

в) Для делимости числа на без остатка необходимо и достаточно чтобы оно заканчивалось на нуль.

В этой главе было изложено понятие сравнения, алгоритм Евклида, теорема Эйлера, разложение чисел в цепные дроби. Рассмотрены сравнения по модулю, свойства сравнений, сравнения различных степеней, теоремы, признаки делимости и арифметика остатков. Так же в этой главе представлены некоторые способы решения задач и наиболее используемые на практике следствия и факты. Рассмотренное нами в главе I имеет широкий спектр применения и намного упрощает решение различных задач. Некоторые виды задач представлены в главе II.

Глава II. Типология задач по теме «Сравнения по модулю и арифметика остатков». Примеры решения задач.

Текстовые задачи

Текстовые задачи могут быть решены алгебраическим, арифметическим и графическим методом. В этой главе мы будем рассматривать только арифметический метод.

Задача 1. Автобус идет из города в город часов. Он выходит из в часов утра. В котором часу автобус прибывает в город ?

Решение. Вспомнив, что в сутках часа, поделим число на :

Значит, автобус идет из в двое суток и часа. Следовательно, он прибудет в в часов.

Ответ: автобус прибудет в часов.

Зачача 2. На пошив одного пододеяльника требуется м полотна. Сколько пододеяльников можно сшить из м полотна? Сколько полотна останется?

Решение. Представим число по модулю :

Следовательно, из м полотна можно сшить пододеяльника и м полотна останется.

Ответ: пододеяльника можно сшить, м полотна останется.

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

Решение. Представим число по модулю :

Так как , то для перевозки т зерна потребуются вагонов вместимостью по т. неполное частное и еще нужен вагон, чтобы увезти остаток в т. Итого вагонов.

Если вагон вмещает т зерна, то

, вагонов.

Ответ: Потребуется 13 вагонов, потребуется 19 вагонов.

Задача 4. В некотором месяце четверга пришлись на четные числа. Какой день недели был числа этого месяца?

Решение:

В месяце четных четверга, значит всего четвергов т.к. в неделе дней, то четверги чередуются: четный и нечетный.

Первый четверг – может быть , или числом, если в месяце день, и или числом, если в месяце дней.

Значит: Первый четверг – число, а Пятый четверг: , следовательно, число – это воскресенье.

Ответ: число – это воскресенье

Задача 5. Расстояние между станциями и равно км. Одновременно из и из навстречу друг-другу выходят два поезда. Поезд вышедший из прибывает на станцию не ранее чем ч., если бы ее скорость была в раза больше, чем на самом деле, то он встретил бы второй поезд, раньше чем ч. после своего выхода из . Скорость какого поезда больше?

Решение. Первый поезд (из пункта ) проходит км за время часов. Значит, его скорость меньше, чем км/ч. Увеличенная в скорость будет меньше чем км/ч. За ч. Первый поезд пройдет расстояние меньше км.

Тогда второй поезд (из пункта до встречи с поездом пройдет путь больше км. Следовательно, скорость второго больше км/ч.

Так как км/ч, а скорость км/ч. Можно сделать вывод о том, что скорость поезда, вышедшего из пункта больше.

Ответ: скорость поезда больше.

Задача 6. Одна бригада рабочих может выполнить задание за дней, а вторая – за дней. Первая бригада работала над выполнением этого задания дня, оставшуюся работу выполнила вторая бригада. За сколько дней было выполнено задание?

1) (задания) – выполнит первая бригада за один день;

2) (задания) - выполнила первая бригада за три дня;

3) (задания) – выполнила вторая бригада;

4) (задания) – выполнит вторая бригада за один день;

5) (дней) – работала вторая бригада;

6) (дней) – затрачено на выполнение задания.

Ответ: задание было выполнено за дней.

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

Этот параграф содержит чрезвычайно полезную информацию, связанную с делимостью чисел. Этот материал выходит за рамки обязательной программы школьного курса математики, но данные задачи встречаются в материалах ОГЭ и ЕГЭ.

Задача 7. Найдите все числа, при делении которых на в частном получится то же число, что и в остатке.

Решение. Пусть при делении числа a на в частном получится то же число, что и в остатке. Тогда . Так как это остаток при делении на , то может быть равно только , , , или . Для всех значений найдем соответствующее значение : , , , , .

Ответ: , , , , .

Задача 8. Число при делении на дает остаток . Какой остаток оно дает при делении на ?

Решение. Пусть число при делении на дает остаток , тогда , тогда при делении на дает остаток .

Ответ:

Задача 9. Докажите, что числа вида , где , не могут при делении на давать остаток .

Доказательство. Остаток от деления на число произведения натуральных чисел равен остатку от деления на число произведения , где и – остатки от деления на чисел и соответственно.

Таким образом, остаток от деления числа на равен остатку от деления на , то есть равен . Остаток от деления числа на равен остатку от деления на , то есть равен . Остаток от деления числа на равен . Так как любое натуральное число всегда можно представить в одном из видов: , , , то при делении на не может давать в остатке .

Задача 10. При каких простых число также является простым?

Решение. Проверим, каким может быть остаток от деления числа на :

1) Если не делится на , то при делении на даёт остаток , тогда при делении на даёт такой же остаток, как и число , то есть . Таким образом, если не делится на , то делится на , но , а простых чисел, делящихся на , кроме числа , не бывает.

2) Единственное простое число, которое делится на это число , следовательно, осталось проверить только случай : не является простым.

В итоге мы доказали, что не существует простых чисел , таких, что число простое.

Ответ:

Задача 11. По тарифному плану «Включайся!» компания сотовой связи каждый вечер снимает со счёта абонента руб. Если на счету осталось меньше руб., то на следующее утро номер блокируют до пополнения счёта. Сегодня утром у Лизы на счету было руб. Сколько дней (включая сегодняшний) она сможет пользоваться телефоном, не пополняя счёт?

Решение. Разделим число на , получим . Принимая во внимание условие «если на счету осталось меньше руб., то на следующее утро номер блокируют до пополнения счёта», мы приходим к выводу, что Лиза сможет пользоваться тарифным планом не дней, а .

Ответ: Лиза сможет пользоваться тарифным планом, не пополняя счет 15 дней.

Задача 12. Придумайте число, при делении которого:

а) на получается остаток ;

б) на получается остаток .

Решение. а) Запишем известные нам данные, получим:

Подставляем числа , , , и тд.

При получим, . Следовательно, число искомое, но не единственное. Например, эти условия будут выполняться для , получим . То есть ответом может являться любое число, которое удовлетворяет условию.

б) Запишем известные нам данные, получим:

Подставляем числа , , , и тд.

При получим, . Следовательно, число 77 искомое.

Ответ: а) 50, б) 77.

Задача 13. Доказать, что выражение делится на .

Решение. Число больше, чем число . Из этого возникает вопрос: на какое число можно заменить число с точки зрения делимости на ?

Представим число как: . Значит, число мы можем представить как используя следствие 1, получаем: .

Так как число это с точки зрения делимости на , то

Ответ: выражение делится на .

Задача 14. Доказать, что сумма чисел делится на .

Решение. Представим числа и по модулю , получим

Следовательно, , а значит выполнимо и следующее сравнение . Таким образом, мы можем сделать вывод о том, что сумма этих чисел делится на .

Ответ: сумма чисел делится на .

Задачи на нахождение последних цифр десятичного числа

Задача 15. Выясним, на какую цифру оканчивается число

Решение. Рассмотрим последовательные степени двойки:

, , , , , , , ,...

Легко заметить, что последние цифры этих чисел повторяются через .

Из этого следует, что последняя цифра числа зависит от того, какой остаток дает при делении на :

при , делящимся на , то есть при , все числа вида оканчиваются на ,

при ,

при ,

при .

Остаток от деления числа 165 на равен , поэтому число оканчивается на .

Ответ: число оканчивается на .

Задача 16.В системе счисления с некоторым основанием десятичное число записывается как . Укажите это основание.

Решение.

Ответ:

Задача 17. Укажите через запятую в порядке возрастания все основания систем счисления, в которых запись числа 22 оканчивается на 4.

Решение:

Из исследования цифр в тексте задачи вытекает, что основанием является число, которое больше либо равно 5.

Если бы в каноническом разложении числа фигурировало слагаемое , где , данное число должно быть больше либо равно , но оно равно , поэтому в разложении числа не присутствует такое слагаемое.

Точно так же, в разложении не могут участвовать более высокие степени с основанием и степени с большим основанием.

Разложение данного числа по степеням имеет вид . Следовательно, . Из разложения числа на множители следуют наборы: .

Ответ:.

Задача 18. Можно ли составить из цифр , , , (каждую цифру можно использовать неограниченное количество раз) два числа, одно из которых в раз больше другого?

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

Рассмотрим все возможные варианты:

1) последняя цифра числа – это цифра , тогда последняя цифра числа – это цифра , но не может содержать в своей записи цифру .

2) последняя цифра числа – это цифра , тогда последняя цифра числа – это цифра , но не может содержать в своей записи цифру .

3) последняя цифра числа – это цифра , тогда последняя цифра числа – это цифра , но не может содержать в своей записи цифру .

4) последняя цифра числа – это цифра , тогда последняя цифра числа – это цифра , но не может содержать в своей записи цифру .

Таким образом, подходящих и не существует.

Ответ: нет.

Сравнения первой степени с одним неизвестным.

Сравнение второй степени по простому модулю.

Метод подбора (проб): решение сравнения находят путем непосредственного подбора наименьших неотрицательных или абсолютно наименьших вычетов по модулю .

Задача 19. Решите сравнение .

Решение. Так как НОД , то по теореме сравнение имеет только одно решение. Подставляя наименьшие по абсолютной величине вычеты , , , по модулю в сравнение , в результате получим, что искомое решение сравнения.

Ответ: .

Задача 20. Решите сравнение .

Решение. Так как НОД и не делится на , то сравнение решений не имеет.

Ответ: решений нет.

Задача 21. Решите сравнение .

Решение. Так как НОД , то по теореме сравнение имеет только одно решение. Подставляя наименьшие по абсолютной величине вычеты по модулю в исходное сравнение получим, что .

Ответ: 2.

Метод преобразования коэффициентов: с помощью свойств сравнений, коэффициенты сравнения преобразуют так, чтобы коэффициент при стал равен .

В сравнении к левой части прибавим :

Так как НОД , то мы можем разделить обе части сравнения на :

Задача 22. Решите сравнение .

Решение. Здесь НОД и делится на .Из этого следует, что сравнение имеет решения.

После деления обеих частей сравнения и модуля на получим сравнение . Полученное сравнение имеет только одно решение, так как НОД Его решением является . Тогда , , решения данного сравнения.

Ответ:, , .

При изучении сравнений 2-й степени рационально использовать символ Лежандра. Введение этого символа, как мы рассмотрим далее, значительно упрощает запись многих результатов и облегчает вычисления.

Задача 23. Решите сравнение .

Решение. Вычисляем символ Лежандра , из этого следует, что сравнение можно решить. Число представим в виде , то есть . Так как , находим решение: .

Проверка: .

Ответ: .

Задача 24. Решите сравнение .

Решение. Вычислим символ Лежандра , следовательно, сравнение разрешимо. Число представляем в виде , . Так как , находим решение: .

Проверка: .

Ответ: .

Обобщение методов, используемых при решении задач

Метод подбора;

Метод преобразования коэффициентов;

Решение сравнений с помощью символа Лежандра;

Решение сравнений с помощью свойств сравнений;

5) Решение сравнений с помощью теоремы Эйлера и алгоритма Евклида;

Решение сравнений с помощью определения сравнения по модулю.

В этой главе мы рассмотрели применение теоретических знаний на практике. Выделили основную типологию задач. Разобрали в соответствии с теорией методы решения задач. Представили значимость владения темой и этими методами при решении задач. Были рассмотрены задачи школьного уровня, ЕГЭ и ОГЭ, а также задачи повышенного уровня сложности. Обобщили методы решения задач.

Заключение

Данная тема является действительно актуальной, поскольку сравнения имеют широкое применение в различных областях науки, техники, экономики. Кроме того, эта тема имеет большое значение, так как она встречается в заданиях повышенной сложности, которые содержатся в дидактических материалах, олимпиадных задачах, заданиях вступительных экзаменов в ВУЗы и на ЕГЭ.

В данной работе изложены вопросы, которые касаются понятия сравнения по модулю, их свойств и арифметики остатков.Были представлены алгоритм Евклида, теорема Эйлера, символ Лежандра, разложение чисел в цепные дроби. Рассмотрены сравнения различных степеней, теоремы, признаки делимости.

Разработана типология задач по теме «Сравнения по модулю и арифметика остатков»:

1) Текстовые задачи;

2) Задачи на деление с остатком;

3) Задачи на нахождение последней цифры десятичного числа;

4) Сравнения первой степени с одним неизвестным. Сравнение второй степени по простому модулю.

Обобщение методов, используемых в решении задач по теме «Сравнения по модулю и арифметика остатков, позволило выделить следующие приемы:

1) Метод подбора;

2) Метод преобразования коэффициентов;

3) Решение сравнений с помощью символа Лежандра;

4) Решение сравнений с помощью свойств сравнений;

5) Решение сравнений с помощью теоремы Эйлера и алгоритма Евклида;

6) Решение сравнений с помощью определения сравнения по модулю.

Список использованных источников

Алгебра и теория чисел: учебное пособие для студентов-заочников II курса физико-математических факультетов педагогических институтов / Н.А. Казачек, Г.Н. Перлатов, Н.Я. Виленкин, А.И. Бородин. М.: Просвещение, 1984. 192 с.

Бачурин В.А. Задачи по элементарной математике и началам математического анализа / В.А Бачурин. М.: ФИЗМАЛИТ, 2005. 712 с.

Булатова А.Г. Сравнения по модулю и арифметика остатков / Сборник XXII студенческой научно-практической конференции «Студенчество в научном поиске».

Бухштаб А.А. Теория чисел: учебное пособие для вузов / А.А. Бухштаб. М.: Просвещение, 1966. 384 с.

Гашков С.Б., Чубариков В.Н., Садовничий В.А. Арифметика. Алгоритмы. Сложность вычислений. 3-е издание, исправленное. Дрофа, 2005. 320 с.

Дэвенпорт Г. Высшая арифметика. Введение в теорию чисел. М.: Наука, 1965. 176 с.

Егоров А.А. Сравнения по модулю и арифметика остатков / А.А. Егоров // Квант. 1970. №5. С. 27-33.

Избранные нестандартные задачи по математике. Ч. 1: учебное пособие / А.И. Сюсюкалов, Е.А. Сюсюкалова; М-во образования и науки Российской Федерации, Рязанский гос. радитехнический ун-т. Рязань: Изд-во Рязанского ин-та развития образования, 2012. 114 с.

Казачек Н.А. и др. Алгебра и теория чисел (под общей редакцией Н.Я. Виленкина). М.: Просвещение, 1979.

Карацуба А.Л. Основы аналитической теории чисел. 2-е изд, 2003. 237 с.

Михелович Ш.Х. Теория чисел: учебное пособие для физ.-мат. факультетов пед. институтов. – М.: Высшая школа, 1967. – 336 с.

Моденов П.С. Сборник задач по специальному курсу элементарной математики. – М.: Высшая школа, 1960.

Монахов В.С. Алгебра и теория чисел : учебное пособие / В.С. Монахов, А.В. Бузланов. – Минск: Изд. центр БГУ, 2007.

Нестеренко Ю.В. Теория чисел: учебник для студентов высших учебных заведений. М.: Издательский центр «академия», 2008. 272 с.

Никитин Н.Д. Алгебра и теория чисел: Учебное пособие. Пенза: Изд-во ПГПУ, 2010. 96 с.

Просветов Г.И. Теория чисел: задачи и решения: Учебно-практическое пособие. М.: Издательство «Альфа-Пресс», 2010. 72 с.

Сборник задач по математике для поступающих во ВТУЗы / В. К. Егерев, В. В. Зайцев, Б. А. Кордемский и др., под. ред. М. И. Сканави. – М.: Мир и образование, 2013.

Совертков П.И. Поиск обратных задач для формирования процедурного компонента образования [Электронный ресурс] / П. И. Совертков, С.Р. Мугаллимова. // Северный регион: наука, образование, культура: Научный и культурно-просветительский журнал. – Сургут, 2010. № 2. С. 57-63.

Черемсина М.И. Избранные вопросы алгебры и теории чисел: учебное пособие / М.И. Черемсина; Министерствово образования и науки РФ; Государственный педагогический университет. – Оренбург: Издательство ОГПУ, 2011. 23 с.

Шидловский А.Б. Диофантовы приближения и трансцендентные числа. — М. : Физматлит, 2007.

Код для цитирования: Скопировать