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

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

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

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

a=sp+r, (1)

где s — число, и r одно из чисел 0,1, . p−1.

1 ) В данной статье под словом число будем понимать целое число.

Действительно. Если s получит значение от −∞ до +∞, то числа sp представляют собой совокупность всех чисел, кратных p. Рассмотрим числа между sp и (s+1)p=sp+p. Так как p целое положительное число, то между sp и sp+p находятся числа

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

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

(2)

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

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

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

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

где s и s1 некоторые целые числа.

Разность этих чисел

(3)

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

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

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

По утверждению a−b делится на p. Следовательно rr1 тоже делится на p. Но т.к. r и r1 числа 0,1. p−1, то абсолютное значение |rr1| Свойство 1. Для любого a и p всегда

a≡a mod (p).

Свойство 2. Если два числа a и c сравнимы с числом b по модулю p , то a и c сравнимы между собой по тому же модулю, т.е. если

a≡b mod (p), b≡c mod (p).
a≡c mod (p).

Действительно. Из условия свойства 2 следует a−b и b−c делятся на p. Тогда их сумма a−b+(b−c)=a−c также делится на p.

a≡b mod (p) и m≡n mod (p),
a+m≡b+n mod (p) и a−m≡b−n mod (p).

Действительно. Так как a−b и m−n делятся на p, то

(a−b)+ (m−n)=(a+m)−(b+n) ,
(a−b)−(m−n)=(a−m)−(b−n)

также делятся на p.

Это свойство можно распространить на какое угодно число сравнений, имеющих один и тот же модуль.

a≡b mod (p) и m≡n mod (p),
am≡bn mod (p).

Действительно.Так как a−b делится на p, то (a−b)m также делится на p, следовательно

am≡bm mod (p).

Далее m−n делится на p, следовательно b(m−n)=bm−bn также делится на p, значит

bm≡bn mod (p).

Таким образом два числа am и bn сравнимы по модулю с одним и тем же числом bm, следовательно они сравнимы между собой (свойство 2).

a≡b mod (p).
a k ≡b k mod (p).

где k некоторое неотрицательное целое число.

Действительно. Имеем a≡b mod (p). Из свойства 4 следует

a·a≡b·b mod (p).
a·a·a≡b·b·b mod (p).
.
a k ≡b k mod (p).

Все свойства 1-5 представить в следующем утверждении:

Утверждение 4. Пусть f(x1, x2, x3, . ) целая рациональная функция с целыми коэффициентами и пусть

a1b1, a2b2, a3b3, . mod (p).
f(a1, a2, a3, . )≡f(b1, b2, b3, . ) mod (p).

При делении все обстоит иначе. Из сравнения

am≡bm mod (p)

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

a≡b mod (p).

Утверждение 5. Пусть

am≡bm mod (p),
a≡b mod (p/λ),

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

m=m1λ и k=k1λ.

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

имеет нулевой остаток. Тогда

.

имеет нулевой остаток, т.е. m1(a−b) делится на k1. Но числа m1 и k1 числа взаимно простые. Следовательно a−b делится на k1=k/λ и, тогда, a≡b mod (p/λ).

Утверждение 6. Если

a≡b mod (p)

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

a≡b mod (m).

Действительно. a−b делится на p. p делится на m. Следовательно a−b делится на m.

Утверждение 7. Если

a≡b mod (p), a≡b mod (q), a≡b mod (s)
a≡b mod (h),

где h наименьшее общее кратное чисел p,q,s.

Действительно. Разность a≡b должна быть числом, кратным p,q,s. и, следовательно должна быть кратным h.

В частном случае, если модули p,q,s взаимно простые числа, то

a≡b mod (h),

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

§ 1. Определение сравнения

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

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

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

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

Читайте также:  Php как получить url текущей страницы

которая читается так:

а сравнимо с b по модулю m.

Делитель m мы предполагаем положительным; он называется модулем сравнения. Наше высказывание (7.1.1) означает, что

a — b = mk, где k — целое число. (7.1.2)

1) 23 ≡ 8 (mod 5), так как 23 — 8 = 15 = 5 3;

2) 47 ≡ 11 (mod 9), так как 47–11 = 36 = 9 4;

3) —11 ≡ 5 (mod 8), так как — 11 — 5 = —16 = 8 (-2);

4) 81 ≡ 0 (mod 27), так как 81 — 0 = 81 = 27 3.

Последний пример показывает, что вообще, вместо того, чтобы говорить: число а делится на число m, мы можем записать

так как это означает, что

где k — некоторое целое число. Например, вместо того, чтобы сказать, что а — четное число, мы можем записать

Таким же образом видно, что нечетное число является числом, удовлетворяющим сравнению

Эта несколько странная терминология является довольно обычной для математических работ.

§ 2. Некоторые свойства сравнений

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

это является следствием того, что

Это следует из того, что b — a = — (а — b) = m(—k).

следует, что аc (mod m), потому что первые два утверждения означают, что

Пример. Из того, что 13 ≡ 35 (mod 11) и 35 ≡ — 9 (mod 11) следует, что 13 ≡ — 9 (mod 11).

Мы говорили, что сравнения похожи по своему свойству на равенства. В действительности, мы можем рассматривать равенства как тип сравнения, а именно, сравнения по модулю 0. По определению,

Вы почти никогда не встретите такую форму сравнения для записи уравнений в математической литературе. Но существует другое сравнение, очевидно, довольно тривиальное, которое иногда используется. Когда модуль есть число m = 1, мы имеем, что

для любой пары целых чисел а и b, так как это означает, что

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

Пример. 8 1/3 ≡ 1 1/3 (mod 1), или

8,333… ≡ 1,333… (mod 1).

Вернемся к свойствам обычных сравнений целых чисел; с этого момента мы будем всегда считать, что модуль является целым числом т ≥ 2.

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

где k — некоторое целое число, а r— одно из чисел

Это является незначительным обобщением деления положительных чисел, описанного в § 3 главы 4. Здесь мы также называем число r в формуле (7.2.6) остатком при делении числа а на число m или остатком по модулю m.

1) а = 11, m = 7, 11 = 7 1 + 4,

2) а = —11, m = 7, —11 = 7 (—2) + 3.

Деление (7.2.6) может быть также записано как сравнение

Таким образом, каждое число сравнимо со своим остатком по модулю m. В приведенных выше примерах мы имеем

11 ≡ 4 (mod 7), — 11 ≡ 3 (mod 7).

Никакие два остатка в (7.2.7) не сравнимы по (mod m), так как разность между любыми двумя из них меньше, чем m. Поэтому два числа, которые не сравнимы по (mod m), должны иметь разные остатки. Итак, мы делаем вывод:

сравнение аb(mod m) выполняется тогда и только тогда, когда числа а и b имеют одинаковые остатки при делении на число m.

Существует другой способ представления этого сравнения. Предположим на мгновение, что а и b — целые положительные числа. Мы видели при обсуждении системы чисел в § 2 главы 6, что когда число а записано при основании m,

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

сравнение аb (mod m) выполняется для целых (положительных) чисел а и b тогда и только тогда, когда числа а и b имеют одинаковые последние цифры в записи при основании m.

так как эти два числа имеют одну и ту же последнюю цифру в десятичной системе чисел.

1. Найдите остатки —37(mod 7), — 111 (mod 11), — 365 (mod 30).

§ 3. Алгебра сравнений

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

По определению, это означает, что

где k и l — целые числа. Сложим уравнения (7.3.2).

В результате получаем

что можем записать как

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

11 ≡ —5 (mod 8) и 7 = — 9 (mod 8). (7.3.5)

Складывая их, получаем

Оба эти сравнения справедливы.

Можно также перемножить два сравнения. Из (7.3.1) и (7.3.2) следует, что

Пример. Когда два сравнения из (7.3.5) перемножены, получается

Сравнение ab (mod m) может быть умножено на любое целое число с, при этом получаем

Это можно рассматривать как частный случай умножения сравнений (7.3.6) при с = d. Его можно также рассматривать как прямое следствие из определения сравнения.

Пример. Когда первое сравнение из (7.3.5) умножается на 3, получаем, что

Читайте также:  Thermaltake toughpower grand rgb sync

Возникает естественный вопрос: в каком случае можно в сравнении (7.3.7) сократить общий множитель с и получить при этом верное сравнение

Именно здесь сравнения отличаются от уравнений. Например, верно, что

но сокращение на множитель 2 дало бы сравнение

В одном важном случае сокращение допустимо:

если асbc (mod m), то ab (mod m) при условии, что числа m и с взаимно просты.

Доказательство. Первое сравнение означает, что

Если D(m, с) = 1, то отсюда следует, что а — b делится на m в соответствии с результатом, доказанным в § 2 главы 4.

мы можем сократить на множитель 4, так как D(11, 4) = 1. Это дает

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

§ 4. Возведение сравнений в степень

Предположим вновь, что имеется сравнение

Как мы только что видели, можно умножить это сравнение на себя, получив

Вообще можно, умножив это сравнение на себя нужное количество раз, получить

для любого целого положительного числа m.

после возведения в квадрат следует сравнение

а после возведения в куб получаем сравнение

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

Одним из путей для выполнения этого является повторное возведение в квадрат. Мы находим:

9 = 3 2 ≡ 2 (mod 7),

89 = 64 + 16 + 8 + 1 = 2 6 + 2 4 + 2 3 + 1,

то отсюда следует, что

3 89 = 3 64 • З 16 • З 8 • 3 = 4 • 4 • 2 • 3 ≡ 5 (mod 7).

Таким образом, остаток (по модулю 7) есть 5, или, говоря другими словами, в соответствии с изложенным в § 2, последняя цифра числа З 89 , записанного в системе счисления при основании 7, равна 5.

В действительности, для того чтобы найти этот остаток, мы записали показатель степени

89 = 2 6 + 2 4 + 2 3 + 1 = (1, 0, 1, 1, 0, 0, 1)

в двоичной системе счисления. Повторным возведением в квадрат мы нашли остатки (по модулю 7) тех степеней числа 89, которые сами являются степенями числа 2:

1, 2, 4, 8, 16, 32, 64.

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

откуда заключаем, что

3 84 = (3 6 ) 14 ≡ 1 (mod7).

3 89 = 3 84 • 3 3 • 3 2 ≡ 1 • (-1) • 2 = -2 ≡ 5 (mod 7),

В качестве другой иллюстрации сказанного можно рассмотреть числа Ферма, с которыми мы познакомились в § 3 гл. 2:

Первые пять чисел Ферма таковы:

Отсюда можно высказать предположение:

десятичная запись всех чисел Ферма, за исключением F и F1 оканчивается цифрой 7.

Докажем с помощью сравнений, что это действительно так. Очевидно, что оно равносильно утверждению, что числа

оканчиваются цифрой 6. Это можно доказать по индукции. Заметим, что

2 2² = 16 ≡ 6 (mod 10),

2 2³ = 256 ≡ 6 (mod 10),

2 2ˆ4 = 65536 ≡ 6 (mod 10),

Более того, если мы возводим в квадрат число 2 2ˆk , то результатом будет число

Предположим, что для некоторого значения t

;

возводя в квадрат это сравнение, мы находим, что

,

что и требовалось.

§ 5. Теорема Ферма

Из алгебры мы знаем правила возведения бинома в степень:

Здесь первый и последний коэффициенты равны единице. Средними биномиальными коэффициентами являются

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

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

Однако знаменатель не содержит простого множителя р, поэтому после сокращения число р останется множителем в числителе. Мы делаем вывод.

Все биномиальные коэффициенты (кроме первого и последнего) в выражении (7.5.2) делятся на р, если р — простое число.

Пусть теперь х и у в выражении (7.5.2) будут целыми числами. Если мы рассмотрим формулу (7.5.2) как сравнение по модулю р, то можно сделать вывод, что для любых целых чисел х и у и простого р

В качестве примера возьмем р = 5:

Так как все средние коэффициенты делятся на 5, то

в соответствии с (7.5.5).

Из сравнения (7.5.5) можно сделать важные выводы. Применим его для случая х = у = 1. Получаем

Возьмем затем х = 2, у = 1 и найдем, что

теперь, используя предыдущий результат, 2 p ≡ 2 (mod p), получаем

Итак, 3 p ≡ 3 (mod p). Далее для х = 3, у = 1 получаем

Используя этот процесс, можно доказать по индукции, что а pa (mod p) для всех значений числа

Случаи a = 0 и а = 1 очевидны. Так как каждое число сравнимо (mod р) с одним из остатков, записанных в (7.5.6), мы делаем вывод:

для любого целого числа а и любого простого числа р

Это утверждение обычно называют теоремой Ферма, хотя некоторые авторы называют ее малой теоремой Ферма, чтобы отличить от последней теоремы Ферма, или гипотезы Ферма, о которой мы упоминали в § 3 главы 5.

Пример. Для р = 13 и а = 2 мы находим: 13 = 8+ 4 + 1, т. е. 2 13 = 2 8+4+1 = 2 8 2 4 • 2 1 . Так как 2 4 = 16 ≡ 3 (mod 13), 2 8 ≡ 9(mod 13), то

2 13 = 2 8 • 2 4 • 2 ≡ 9 • 3 • 2 ≡ 2 (mod 13),

как и утверждает теорема Ферма.

В соответствии с правилом сокращения для сравнений, сформулированном в конце § 3, мы можем сократить общий множитель а в обеих частях записи теоремы Ферма (7.5.7) при условии, что число а взаимно просто с числом р, являющимся модулем сравнения. Это дает следующий результат:

Читайте также:  Как настроить резкость на ноутбуке

если а является целым числом, не делящимся на простое число р, то

Этот результат также называют теоремой Ферма.

Пример. Когда а = 7, р = 19, мы находим, что

7 2 = 49 ≡ 11 (mod 19)

7 4 ≡ 121 ≡ 7 (mod 19),

7 8 ≡ 49 ≡ 11 (mod 19),

7 16 ≡ 121 ≡ 7 (mod 19),

a p -1 = 7 18 = 7 16 • 7 2 ≡ 7 • 11 ≡ 1 (mod 19),

что соответствует утверждению (7.5.8).

В качестве приложения теоремы Ферма вновь рассмотрим треугольники Пифагора, обсужденные в гл. 5 и докажем следующее утверждение:

произведение длин сторон треугольника Пифагора делится на 60.

Доказательство. Очевидно, достаточно доказать это для простейших треугольников. В соответствии с формулой (5.2.7), это произведение есть

Число Р делится на 60 тогда и только тогда, когда оно делится на 4, на 3 и на 5. Так как одно из чисел m и n четно, то 2mn, а следовательно, и число Р, делится на 4. Оно делится на 3, если хотя бы одно из чисел m или n делится на 3, но если ни одно из них не делится на 3, то Р все же будет делиться на 3, так как из условий (7.5.8), а также D(m, 3) = 1 и D (n, 3) = 1 следует, что m 2 ≡ 1 (mod 3) и n 2 ≡ 1 (mod 3), так что

m 2 — n 2 ≡ 1 – 1 = 0 (mod 3).

Аналогично, число Р делится на 5. Это очевидно, если m или n делится на 5. Если ни одно из них не делится на 5, то вновь по теореме Ферма (7.5.8) получаем

m 4 — n 4 ≡ 1 – 1 = 0 (mod 5).

Так, 3 ≡ 1 (mod 2), 7 ≡ 1 (mod 3). Два числа сравнимы по модулю 2, если они оба четны, либо если они оба нечетны. По модулю 1 все целые числа сравнимы между собой.

В том случае, если число делится на , то оно сравнимо с нулем по модулю :

mod ).

Свойства сравнений по модулю вытекают из свойств арифметических операций.

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

  • Пусть mod ), mod ). Тогда:
  • mod ),
  • mod ),
  • mod ).
  • Пусть mod ), и числа и взаимно просты. Тогда mod ).
  • Отметим, что обе части сравнения не всегда можно сократить на какой-либо множитель. Так, 6 ≡ 3 (mod 3), но 2 не сравнимо с 1 по этому же модулю.

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

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

    Признак делимости на 2. Число, делящееся на 2, называется чётным , не делящееся на 2 – нечётным . Число делится на 2 тогда и только тогда, когда его последняя цифра делится на 2.

    Признак делимости на 5. Число делится на 5 тогда и только тогда, когда его последняя цифра – 5 или 0.

    Признак делимости на 25. Число делится на 25 тогда и только тогда, когда две его последние цифры либо нули, либо образуют число, делящееся на 25.

    Признаки делимости на 10, 100, 1000. Число делится на 10 тогда и только тогда, когда его последняя цифра – 0. Число делится на 100 тогда и только тогда, когда две его последние цифры – нули. Число делится на 1000 тогда и только тогда, когда три его последние цифры – нули.

    Признак делимости на 4. Число делится на 4 тогда и только тогда, когда две его последние цифры – нули, либо когда двузначное число, образованное двумя его последними цифрами, делится на 4.

    Признак делимости на 3. Число делится на 3 тогда и только тогда, когда сумма его цифр делится на 3.

    Признак делимости на 9. Число делится на 9 тогда и только тогда, когда сумма его цифр делится на 9.

    Признак делимости на 11. Число делится на 11 тогда и только тогда, когда сумма его цифр, стоящих на нечётных местах, либо равна сумме цифр, стоящих на чётных местах, либо отличается от неё на число, кратное 11.

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

    Произвольное число где – цифры числа в десятичной записи. Так как 10 ≡ 1 (mod 9), то 10 2 ≡ 1 (mod 9) и вообще ≡ 1 (mod 9) для любого натурального . Отсюда Теорема доказана.

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

    Для любого натурального верно равенство , где 1 – число единиц, 2 – число десятков этого числа. Пусть (то есть – число десятков, сложенное с удвоенным числом единиц). Тогда ≡ 0 (mod 19), откуда следует, что ≡ 0 (mod 19) тогда и только тогда, когда ≡ 0 (mod 19), то есть ≡ 0 (mod 19). Утверждение доказано.

    В заключение этого параграфа приведем формулировку малой теоремы Ферма.

    Малая теорема Ферма

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

    mod ).

    В частности, если – простое число, – натуральное число, взаимно простое с , то

    mod ).

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

    Воспользуемся малой теоремой Ферма: mod ). Положим Тогда 10 16 ≡ 1 (mod 17) или 10 16 – 1 ≡ 0 (mod 17). Число 10 16 – 1 состоит из 16 девяток. Это и есть одно из чисел, которые делятся на 17 без остатка.

    Ссылка на основную публикацию
    Adblock detector