Проект по математике по теме

«Сравнения по модулю»

Зарипова Айсылу

Советский район города Казани

МБОУ «СОШ №166», 7а класс

Научный руководитель: Антонова Н.А.

Оглавление

Введение____________________________________________________3

    Что такое сравнения________________________________________4

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

      История возникновение понятия сравнений по модулю_____4

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

    Применение сравнений к решению задач______________________6

    1. Простейшим применением сравнений по модулю является определение делимости чисел___________________________6

      Одна задача на сравнения_______________________________8

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

Заключение__________________________________________________10

Список использованной литературы_____________________________11

Введение.

Тема работы: Сравнения по модулю.

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

Цель: Выяснить суть сравнений по модулю, основные методы работы со сравнениями по модулю.

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

Объект исследования: теория чисел.

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

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

I . Что такое сравнения.

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

Числа и называются сравнимыми по модулю, если делится на, другими словами а и в имеют одинаковые остатки при делении на .

Обозначение

Примеры:

    12 и 32 сравнимы по модулю 5, так как 12 при делении на 5 имеет остаток 2 и 32 при делении на 2 имеет остаток 2. Записывается 12 ;

    101 и 17 сравнимы по модулю 21;

    1. История возникновение понятия сравнений по модулю.

В значительной степени теория делимости была создана Эйлером. Определение сравнения было сформулировано в книге К.Ф.Гаусса «Арифметические исследования». Эту работу, написанную на латинском языке, начали печатать в 1797 году, но книга вышла в свет лишь в 1801 году из-за того, что процесс книгопечатания в то время был чрезвычайно трудоемким и длительным. Первый раздел книги Гаусса так и называется: «О сравнении чисел». Именно Гаусс предложил утвердившуюся в математике символику сравнений по модулю.

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

Если

Доказательство:

  1. Если к первому равенству прибавить второе, то получиться

это сумма двух целых чисел, значит, является целым числом, следовательно.

    Если из первого равенства вычесть второе, то получиться

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

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

это разность произведений целых чисел, значит, является целым числом, следовательно.

    Это следствие третьего свойства сравнений.

Что и требовалось доказать.

5) Если .

Доказательство: Найдем сумму двух этих выражений:

это сумма двух целых чисел, значит, является целым числом, следовательно, .

Что и требовалось доказать.

6) Если – целое число, то

Доказательство: , где p – целое число, умножим это равенство на, получим: . Так как – произведение целых чисел, то Что и требовалось доказать.

7) Если

Доказательство: рассуждения аналогичны доказательству свойства 6.

8) Если - взаимно простые числа, то

Доказательство: , поделим это выражение на, получим: - взаимно простые числа, значит, делится на нацело, т.е. =. А это значит, что Что и требовалось доказать.

II . Применение сравнений к решению задач.

2.1. Простейшим применением сравнений по модулю является определение делимости чисел.

Пример. Найдите остаток от деления 2 2009 на 7.

Решение: Рассмотрим степени числа 2:

возводя сравнение в степень 668 и умножая на, получаем: .

Ответ: 4.

Пример. Докажите, что 7+7 2 +7 3 +…+7 4 n делится на 100 при любом n из множества целых чисел.

Решение: Рассмотрим сравнения

и т.д. Цикличность остатков объясняется правилами умножения чисел столбиком. Складывая первые четыре сравнения, получаем:

Значит, эта сумма делится на 100 без остатка. Аналогично, складывая следующие сравнения про четыре, получим, что каждая такая сумма делится на 100 без остатка. Значит, вся сумма, состоящая из 4 n слагаемых, делится на 100 без остатка. Что и требовалось доказать.

Пример. Определите, при каком значении n выражение делится на 19 без остатка.

Решение: .

Умножим это сравнение на 20. Получим.

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

Ответ n – любое натуральное число.

Пример. Какой цифрой оканчивается число.

Решение. Для решения этой задачи будем следить только за последней цифрой. Рассмотрим степени числа 14:

Можно заметить, что при нечетном показателе значение степени оканчивается на 4, а при четном – на 6. Тогда оканчивается на 6, т.е. является четным числом. Значит, будет оканчиваться на 6.

Ответ 6.

2.2. Одна задача на сравнения.

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

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

Один прохожий обнаружил кучу яблок около дерева, на котором сидела мартышка. Пересчитав их, он понял, что если 1 яблоко отдать мартышке, то число оставшихся яблок разделится на n без остатка. Отдав лишнее яблоко мартышке, он взял себе 1/ n оставшихся яблок и ушел. К куче позднее подошел следующий прохожий, затем следующий и т.д. Каждый следующий прохожий, пересчитав яблоки, замечал, что их число при делении на n дает остаток 1 и, отдав мартышке лишнее яблоко, он забирал себе 1/ n оставшихся яблок и шел дальше. После того как ушел последний, n -й прохожий, число яблок, оставшихся в куче, делилось на n без остатка. Сколько яблок было в куче сначала?

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

2.3. Применение сравнений по модулю в профессиональной деятельности.

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

Заключение.

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

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

Список использованной литературы.

    Алфутова Н.Б. Алгебра и теория чисел./Н.Б.Алфутова, А.В.Устинов. М.:МЦНМО, 2002, 466 с.

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

    Виленкин Н. Сравнения и классы вычетов./Н.Виленкин.//Квант. – 1978.- 10.

    Федорова Н.Е. Изучение алгебры и математического анализа. 10 класс. http :// www . prosv . ru / ebooks / Fedorova _ Algebra _10 kl /1/ xht

    ru . wikipedia . org / wiki /Сравнение_по_модулю.

Рассмотрим сравнение вида x 2 ≡a (mod p α), где p – простое нечетное число. Как было показано в п.4 §4, решение этого сравнения можно отыскать, решив сравнение x 2 ≡a (mod p ). Причем сравнение x 2 ≡a (mod p α) будет иметь два решения, если a является квадратичным вычетом по модулю p .

Пример:

Решить квадратичное сравнение x 2 ≡86(mod 125).

125 = 5 3 , 5 – простое число. Проверим, является ли 86 квадратом по модулю 5.

Исходное сравнение имеет 2 решения.

Найдем решение сравнения x 2 ≡86(mod 5).

x 2 ≡1(mod 5).

Это сравнение можно было бы решить способом, указанным в предыдущем пункте, но мы воспользуемся тем, что квадратный корень из 1 по любому модулю есть ±1, а сравнение имеет ровно два решения. Таким образом, решение сравнения по модулю 5 есть

x ≡±1(mod 5) или, иначе, x =±(1+5t 1).

Подставим получившееся решение в сравнение по модулю 5 2 =25:

x 2 ≡86(mod 25)

x 2 ≡11(mod 25)

(1+5t 1) 2 ≡11(mod 25)

1+10 t 1 +25 t 1 2 ≡11(mod 25)

10 t 1 ≡10(mod 25)

2 t 1 ≡2(mod 5)

t 1 ≡1(mod 5), или, что то же самое, t 1 =1+5t 2 .

Тогда решение сравнения по модулю 25 есть x =±(1+5(1+5t 2))=±(6+25t 2). Подставим получившееся решение в сравнение по модулю 5 3 =125:

x 2 ≡86(mod 125)

(6+25t 2) 2 ≡86(mod 125)

36+12·25t 2 +625t 2 2 ≡86(mod 125)

12·25t 2 ≡50(mod 125)

12t 2 ≡2(mod 5)

2t 2 ≡2(mod 5)

t 2 ≡1(mod 5), или t 2 =1+5t 3 .

Тогда решение сравнения по модулю 125 есть x =±(6+25(1+5t 3))=±(31+125t 3).

Ответ: x ≡±31(mod 125).

Рассмотрим теперь сравнение вида x 2 ≡a (mod 2 α). Такое сравнение не всегда имеет два решения. Для такого модуля возможны случаи:

1) α=1. Тогда сравнение имеет решение только тогда, когда a ≡1(mod 2), и решением будет x ≡1(mod 2) (одно решение).

2) α=2. Сравнение имеет решения только тогда, когда a ≡1(mod 4), и решением будет x ≡±1(mod 4) (два решения).

3) α≥3. Сравнение имеет решения только тогда, когда a ≡1(mod 8), и таких решений будет четыре. Сравнение x 2 ≡a (mod 2 α) при α≥3 решается так же, как сравнения вида x 2 ≡a (mod p α), только в качестве начального решения выступают решения по модулю 8: x ≡±1(mod 8) и x ≡±3(mod 8). Их следует подставить в сравнение по модулю 16, затем по модулю 32 и т. д. вплоть до модуля 2 α .

Пример:

Решить сравнение x 2 ≡33(mod 64)

64=2 6 . Проверим, имеет ли исходное сравнение решения. 33≡1(mod 8), значит сравнение имеет 4 решения.

По модулю 8 эти решения будут: x ≡±1(mod 8) и x ≡±3(mod 8), что можно представить как x =±(1+4t 1). Подставим это выражение в сравнение по модулю 16

x 2 ≡33(mod 16)

(1+4t 1) 2 ≡1(mod 16)

1+8t 1 +16t 1 2 ≡1(mod 16)

8t 1 ≡0 (mod 16)

t 1 ≡0 (mod 2)

Тогда решение примет вид x =±(1+4t 1)=±(1+4(0+2t 2))=±(1+8t 2). Подставим получившееся решение в сравнение по модулю 32:

x 2 ≡33(mod 32)

(1+8t 2) 2 ≡1(mod 32)

1+16t 2 +64t 2 2 ≡1(mod 32)

16t 2 ≡0 (mod 32)

t 2 ≡0 (mod 2)

Тогда решение примет вид x =±(1+8t 2) =±(1+8(0+2t 3)) =±(1+16t 3). Подставим получившееся решение в сравнение по модулю 64:

x 2 ≡33(mod 64)

(1+16t 3) 2 ≡33(mod 64)

1+32t 3 +256t 3 2 ≡33(mod 64)

32t 3 ≡32 (mod 64)

t 3 ≡1 (mod 2)

Тогда решение примет вид x =±(1+16t 3) =±(1+16(1+2t 4)) =±(17+32t 4). Итак, по модулю 64 исходное сравнение имеет четыре решения: x ≡±17(mod 64)и x ≡±49(mod 64).

Теперь рассмотрим сравнение общего вида: x 2 ≡a (mod m ), (a ,m )=1, - каноническое разложение модуля m . Согласно Теореме из п.4 §4, данному сравнению равносильна система

Если каждое сравнение этой системы разрешимо, то разрешима и вся система. Найдя решение каждого сравнения этой системы, мы получим систему сравнений первой степени, решив которую по китайской теореме об остатках, получим решение исходного сравнения. При этом количество различных решений исходного сравнения (если оно разрешимо) есть 2 k , если α=1, 2 k +1 , если α=2, 2 k +2 , если α≥3.

Пример:

Решить сравнение x 2 ≡4(mod 21).

Определение 1. Если два числа 1) a и b при делении на p дают один и тот же остаток r , то такие числа называются равноостаточными или сравнимыми по модулю p .

Утверждение 1. Пусть p какое нибудь положительное число. Тогда всякое число a всегда и притом единственным способом может быть представлено в виде

Но эти числа можно получить задав r равным 0, 1, 2,..., p −1. Следовательно sp+r=a получит всевозможные целые значения.

Покажем, что это представление единственно. Предположим, что p можно представить двумя способами a=sp+r и a=s 1 p +r 1 . Тогда

(2)

Так как r 1 принимает один из чисел 0,1, ..., p −1, то абсолютное значение r 1 −r меньше p . Но из (2) следует, что r 1 −r кратно p . Следовательно r 1 =r и s 1 =s .

Число r называется вычетом числа a по модулю p (другими словами, число r называется остатком от деления числа a на p ).

Утверждение 2. Если два числа a и b сравнимы по модулю p , то a−b делится на p .

Действительно. Если два числа a и b сравнимы по модулю p , то они при делении на p имеют один и тот же остаток p . Тогда

делится на p , т.к. правая часть уравнения (3) делится на p .

Утверждение 3. Если разность двух чисел делится на p , то эти числа сравнимы по модулю p .

Доказательство. Обозначим через r и r 1 остатки от деления a и b на p . Тогда

Примеры 25≡39 (mod 7), −18≡14 (mod 4).

Из первого примера следует, что 25 при делении на 7 дает тот же остаток, что и 39. Действительно 25=3·7+4 (остаток 4). 39=3·7+4 (остаток 4). При рассмотрении второго примера нужно учитывать, что остаток должен быть неотрицательным числом, меньшим, чем модуль (т.е. 4). Тогда можно записать: −18=−5·4+2 (остаток 2), 14=3·4+2 (остаток 2). Следовательно −18 при делении на 4 дает остаток 2, и 14 при делении на 4 дает остаток 2.

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

Свойство 1. Для любого a и p всегда

не всегда следует сравнение

где λ это наибольший общий делитель чисел m и p .

Доказательство. Пусть λ наибольший общий делитель чисел m и p . Тогда

Так как m(a−b) делится на k , то

Следовательно

и m является один из делителей числа p , то

где h=pqs.

Заметим, что можно допустить сравнения по отрицательным модулям, т.е. сравнение a≡b mod (p ) означает и в этом случае, что разность a−b делится на p . Все свойства сравнений остаются в силе и для отрицательных модулей.

На n они дают одинаковые остатки.

Эквивалентные формулировки: a и b сравнимы по модулю n , если их разность a - b делится на n , или если a может быть представлено в виде a = b + k n , где k - некоторое целое число. Например: 32 и −10 сравнимы по модулю 7, так как

Утверждение « a и b сравнимы по модулю n » записывается в виде:

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

Отношение сравнения по модулю обладает свойствами

Любые два целых числа a и b сравнимы по модулю 1.

Для того, чтобы числа a и b были сравнимы по модулю n , необходимо и достаточно, чтобы их разность делилась на n .

Если числа и попарно сравнимы по модулю n , то их суммы и , а также произведения и тоже сравнимы по модулю n .

Если числа a и b сравнимы по модулю n , то их степени a k и b k тоже сравнимы по модулю n при любом натуральном k .

Если числа a и b сравнимы по модулю n , и n делится на m , то a и b сравнимы по модулю m .

Для того, чтобы числа a и b были сравнимы по модулю n , представленному в виде его канонического разложения на простые сомножители p i

необходимо и достаточно, чтобы

Отношение сравнения является отношением эквивалентности и обладает многими свойствами обычных равенств. Например, их можно складывать и перемножать: если

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

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

Другие свойства:

Связанные определения

Классы вычетов

Множество всех чисел, сравнимых с a по модулю n называется классом вычетов a по модулю n , и обычно обозначается [a ] n или . Таким образом, сравнение равносильно равенству классов вычетов [a ] n = [b ] n .

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

Операции сложения и умножения на индуцируют соответствующие операции на множестве :

[a ] n + [b ] n = [a + b ] n

Относительно этих операций множество является конечным кольцом , а если n простое - конечным полем .

Системы вычетов

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

0,1,...,n − 1

или абсолютно наименьшие вычеты, состоящие из чисел

,

в случае нечётного n и чисел

в случае чётного n .

Решение сравнений

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

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

Решение такого сравнения начинается с вычисления НОД (a, m)=d . При этом возможны 2 случая:

  • Если b не кратно d , то у сравнения нет решений.
  • Если b кратно d , то у сравнения существует единственное решение по модулю m / d , или, что то же самое, d решений по модулю m . В этом случае в результате сокращения исходного сравнения на d получается сравнение:

где a 1 = a / d , b 1 = b / d и m 1 = m / d являются целыми числами, причем a 1 и m 1 взаимно просты. Поэтому число a 1 можно обратить по модулю m 1 , то есть найти такое число c , что (другими словами, ). Теперь решение находится умножением полученного сравнения на c :

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

Пример

Для сравнения имеем d = 2 , поэтому по модулю 22 сравнение имеет два решения. Заменим 26 на 4, сравнимое с ним по модулю 22, и затем сократим все 3 числа на 2:

Поскольку 2 взаимно просто с модулем 11, можно сократить левую и правую части на 2. В итоге получаем одно решение по модулю 11: , эквивалентное двум решениям по модулю 22: .

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

Решение сравнений второй степени сводится к выяснению, является ли данное число квадратичным вычетом (с помощью квадратичного закона взаимности) и последующему вычислению квадратного корня по данному модулю.

История

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