Сравнение с одним неизвестным x имеет вид
Где . Еслиa n не делится на m , то и называется степенью сравнения.
Решением сравнения называется всякое целое число x 0 , для которого
Если х 0 удовлетворяет сравнению, то, согласно свойству 9 сравнений, этому сравнению будут удовлетворять все целые числа, сравнимые с x 0 по модулю m . Поэтому все решения сравнения, принадлежащие одному классу вычетов по модулю т , будем рассматривать как одно решение. Таким образом, сравнение имеет столько решений, сколько элементов полной системы вычетов ему удовлетворяет.
Сравнения, множества решений которых совпадают, называются равносильными.
Сравнение первой степени с одним неизвестным х имеет вид
(2.2)
Теорема2.4. Для того чтобы сравнение имело хотя бы одно решение, необходимо и достаточно, чтобы число b делилось на НОД(a , m ).
Доказательство.
Сначала
докажем необходимость. Пусть d
=
НОД(a
,
m
)
и
х
0
-
решение сравнения. Тогда
,
то есть разностьах
0
−
b
делится
на т.
Значит,
существует такое целое число q
,
что
ах
0
−
b
=
qm
.
Отсюда
b
= ах
0
−
qm
.
А
поскольку d
,
как
общий делитель, делит числа а
и
т,
то
уменьшаемое и вычитаемое делятся на d
,
а
значит и b
делится
на
d
.
Теперь докажем достаточность. Пусть d - наибольший общий делитель чисел а и т, и b делится на d . Тогда по определению делимости существуют такие целые числа a 1 , b 1 ,т 1 , что.
Расширенным алгоритмом Евклида найдем линейное представление числа 1 = НОД(a 1 , m 1 ):
для некоторых x 0 , y 0 . Домножим обе части последнего равенства на b 1 d :
или, что то же самое,
,
то есть , и- решение сравнения. □
Пример2.10. Сравнение 9х = 6 (mod 12) имеет решение, так как НОД(9, 12) = 3 и 6 делится на 3. □
Пример2.11. Сравнение 6х = 9 (mod 12) не имеет решений, так как НОД(6, 12) = 6, а 9 не делится на 6. □
Теорема 2.5. Пусть сравнение (2.2) разрешимо и d = НОД(a , m ). Тогда множество решений сравнения (2.2) состоит из d классов вычетов по модулю т, а именно, если х 0 - одно из решений, то все другие решения - это
Доказательство.
Пусть
х
0
-
решение сравнения (2.2), то есть
и,
.
Значит,
существует такое q
,
что ах
0
−
b
=
qm
.
Подставляя
теперь в последнее равенство вместо х
0
произвольное
решение вида,
где,
получаем выражение
, делящееся на m . □
Пример 2.12. Сравнение 9х =6 (mod 12) имеет ровно три решения, так как НОД(9, 12)=3. Эти решения: х 0 = 2, х 0 + 4 = 6, х 0 + 2∙4=10.□
Пример2.13. Сравнение 11х =2 (mod 15) имеет единственное решение х 0 = 7,таккакНОД(11,15)=1.□
Покажем, как решать сравнение первой степени. Не умаляя общности, будем считать, что НОД(a , т) = 1. Тогда решение сравнения (2.2) можно искать, например, по алгоритму Евклида. Действительно, используя расширенный алгоритм Евклида, представим число 1 в виде линейной комбинации чисел a и т :
Умножим обе части этого равенства на b , получим: b = abq + mrb , откуда abq - b = - mrb , то есть a ∙ (bq ) = b (mod m ) и bq - решение сравнения (2.2).
Еще
один путь решения - использовать теорему
Эйлера. Опять считаем, что НОД(а, т)
=
1. Применяем теорему Эйлера:
.
Умножим обе части сравнения наb
:
.
Переписывая
последнее выражение в виде
,
получаем, что- решение сравнения (2.2).
Пусть теперь НОД(a , m ) = d >1. Тогда a = a t d , m = m t d , где НОД(а 1 , m 1) = 1. Кроме того, необходимо b = b 1 d , для того чтобы сравнение было разрешимо. Если х 0 - решение сравнения а 1 x = b 1 (mod m 1), причем единственное, поскольку НОД(а 1 , m 1) = 1, то х 0 будет решением и сравнения а 1 xd = db 1 (mod m 1), то есть исходного сравнения (2.2). Остальные d - 1 решений находим по теореме 2.5.
Сравнение чисел по модулю
Подготовила проект: Зутикова Ирина
МАОУ «Лицей №6»
Класс: 10«а»
Научный руководитель: Желтова Ольга Николаевна
Тамбов
2016
Проблема:
Большинство учеников редко используют сравнение чисел по модулю для решений нестандартных и олимпиадных заданий.
Цель проекта:
Показать, как с помощью сравнения чисел по модулю можно решать нестандартные и олимпиадные задания.
Гипотеза:
Более глубокое изучение темы «Сравнение чисел по модулю» поможет ученикам решать некоторые нестандартные и олимпиадные задания.
Задачи проекта и план их достижения:
1.Подробно изучить тему «Сравнение чисел по модулю».
2.Решить несколько нестандартных и олимпиадных заданий, используя сравнение чисел по модулю.
3.Создать памятку для учеников на тему «Сравнение чисел по модулю».
4.Провести урок по теме «Сравнение чисел по модулю» в 10«а» классе.
5.Дать классу домашнее задание по теме «Сравнение по модулю».
6.Сравнить время выполнения задания до и после изучения темы «Сравнение по модулю».
7.Сделать выводы.
Прежде чем начать подробно изучать тему «Сравнение чисел по модулю», я решила сравнить, как она представлена в различных учебниках.
Как я выяснила, в некоторых учебниках эта тема даже не затрагивается, не смотря на углубленный уровень. А наиболее понятно и доступно тема представлена в учебнике Л.Г.Петерсона (Глава: Введение в теорию делимости), поэтому попробуем разобраться в «Сравнении чисел по модулю», опираясь на теорию из этого учебника.
Сравнения и их свойства.
Определение: Если два целых числа a и b имеют одинаковые остатки при делении на некоторое целое число m (m>0), то говорят, что a и b сравнимы по модулю m , и пишут:
Теорема: тогда и только тогда, когда разность aи bделится на m.
Свойства:
Примеры задач и их решения.
1.Найти последнюю цифру числа 3 999 .
Решение:
Т.к. последняя цифра числа - это остаток от деления на 10, то
3 999 =3 3 *3 996 =3 3 *(3 4 ) 249 =7*81 249 7(mod 10)
(Т.к. 34=81 1(mod 10);81 n 1(mod10) (по свойству))
Ответ:7.
2.Доказать,что 2 4n -1 делится на 15 без остатка. (Физтех2012)
Решение:
Т.к. 16 1(mod 15), то
16 n -1 0(mod 15) (по свойству); 16n= (2 4 ) n
2 4n -1 0(mod 15)
3.Доказать, что 12 2n+1 +11 n+2 делится без остатка на 133.
Решение:
12 2n+1 =12*144 n 12*11 n (mod 133) (по свойству)
12 2n+1 +11 n+2 =12*11 n +11 n *121=11 n *(12+121) =11 n *133
Число (11 n *133)без остатка делится на 133. Следовательно,(12 2n+1 +11 n+2 )делится без остатка на 133.
4.Найти остаток от деления на 15 числа 2 2015 .
Решение:
Т.к.16 1(mod 15), то
2 2015 8(mod 15)
Ответ:8.
5.Найти остаток от деления на 17 числа 2 2015 . (Физтех2015)
Решение:
2 2015 =2 3 *2 2012 =8*16 503
Т.к.16 -1(mod 17), то
2 2015 -8(mod 15)
8 9(mod 17)
Ответ:9.
6.Доказать, что число 11 100 -1 делится на 100 без остатка. (Физтех2015)
Решение:
11 100 =121 50
121 50 21 50 (mod 100) (по свойству)
21 50 =441 25
441 25 41 25 (mod 100) (по свойству)
41 25 =41*1681 12
1681 12 (-19) 12 (mod 100) (по свойству)
41*(-19) 12 =41*361 6
361 6 (-39) 6 (mod 100)(по свойству)
41*(-39) 6 =41*1521 3
1521 3 21 3 (mod100) (по свойству)
41*21 3 =41*21*441
441 41(mod 100) (по свойству)
21*41 2 =21*1681
1681 -19(mod 100) (по свойству)
21*(-19)=-399
399 1(mod 100) (по свойству)
Значит 11 100 1(mod 100)
11 100 -1 0(mod 100) (по свойству)
7.Даны три числа: 1771,1935,2222. Найти число, при делении на которое остатки трёх данных чисел будут равны. (ВШЭ2016)
Решение:
Пусть неизвестное нам число будет равно а,тогда
2222 1935(mod a); 1935 1771(mod a); 2222 1771(mod a)
2222-1935 0(moda) (посвойству); 1935-1771 0(moda) (по свойству); 2222-1771 0(moda) (по свойству)
287 0(mod a); 164 0(mod a); 451 0(mod a)
287-164 0(moda) (по свойству); 451-287 0(moda)(по свойству)
123 0(mod a); 164 0(mod a)
164-123 0(mod a) (посвойству)
41
Определение 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 . Все свойства сравнений остаются в силе и для отрицательных модулей.
