Как сравнить числа по модулю

Модуль числа, сравнение чисел

Модуль числа а обозначают $|a|$. Вертикальные черточки справа и слева от числа образуют знак модуля.

Например, модуль любого числа (натурального, целого, рационального или иррационального) записывается так: $|5|$, $|-11|$, $|2,345|$, $|\sqrt[4]<45>|$.

Модуль числа a равен самому числу $a$, если $a$ является положительным, числу $−a$, если $a$ является отрицательным, или $0$, если $a=0$.

Данное определение модуля числа можно записать следующим образом:

$|a|= \begin a, & a > 0, \\ 0, & a=0,\\ -a, &a

Можно использовать более краткую запись:

$|a|=\begin a, & a \geq 0 \\ -a, & a

Вычислить модуль чисел $23$ и $-3,45$.

Найдем модуль числа $23$.

Число $23$ – положительное, следовательно, по определению модуль положительного числа равен этому числу:

Найдем модуль числа $–3,45$.

Число $–3,45$ – отрицательное число, следовательно согласно определению модуль отрицательного числа равен числу, противоположному данному:

Модуль числа является абсолютной величиной числа.

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

Модуль числа как расстояние

Геометрическое значение модуля числа: модуль числа – это расстояние.

Модуль числа a – это расстояние от точки отсчета (нуля) на числовой прямой до точки, которая соответствует числу $a$.

Например, модуль числа $12$ равен $12$, т.к. расстояние от точки отсчета до точки с координатой $12$ равно двенадцати:

Точка с координатой $−8,46$ расположена от начала отсчета на расстоянии $8,46$, поэтому $|-8,46|=8,46$.

Модуль числа как арифметический квадратный корень

Модуль числа a является арифметическим квадратным корнем из $a^2$:

Вычислить модуль числа $–14$ с помощью определения модуля числа через квадратный корень.

Сравнение отрицательных чисел

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

Правило сравнения отрицательных чисел:

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

На числовой прямой меньшее отрицательное число располагается левее большего отрицательного числа.

Сравнить отрицательные числа $−27$ и $−4$.

Согласно правилу сравнения отрицательных чисел найдем сначала модули чисел $–27$ и $–4$, а затем сравним полученные положительные числа.

Таким образом, получаем, что $–27 |-4|$.

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

Сравнение чисел с противоположными знаками

Правило сравнения чисел с противоположными знаками:

Положительное число всегда больше отрицательного, а отрицательное число всегда меньше положительного.

Сравнить целые числа $−53$ и $8$.

Числа имеют противоположные знаки. Согласно правилу сравнения чисел с противоположными знаками получаем, что отрицательное число $−53$ меньше положительного числа $8$.

Сравнить числа $3 \frac<11><13>$ и $–5,(123)$.

Согласно правилу сравнения чисел с противоположными знаками отрицательное число всегда меньше положительного. Следовательно, $–5,(123)

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

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

Числовые сравнения №1

§5 Числовые сравнения

п.1 Определение и основные свойства сравнений

Пусть — произвольное натуральное число. Будем называть его модулем.

Определение: Целые числа a и b сравнимы по модулю m, если их разность a—b делятся на m.

Обозначение: a ≡ b (mod m).

17 ≡ 5 (mod 17), 19 ≡ -1 (mod 10)

15 ≡ 0 (mod 5), 11≡ 1 (mod 5)

Замечание: Сравнение 17 ≡ 5 (mod 12) иллюстрирует хорошо знакомую ситуацию. По модулю 12 мы обычно называем время, говоря «сейчас 5 часов», вместо «сейчас 17 часов».

Теорема 1: Следующее утверждения для целых чисел a и b равносильны:

разность a—b делится на m.

, где .

a и b имеют одинаковые остатки при делении на m.

Доказательство: 1)2) Пусть a—b делятся на m. Тогда a—b=mt

или .

2)3) Пусть , и пусть b при делении на m имеет остаток r, т.е. . Тогда , где 0 ≤ r < m.

Следовательно r — остаток от деления a на m. Значит, a и b имеют равные остатки от деления на m.

3)1) Пусть Тогда делится на m.

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

Перейдем к изучению свойств сравнений. Отношение сравнимости двух целых чисел является примером бинарного отношения на множестве Z. Во многом это отношение похоже на отношение равенства. Свойства 1°—4° иллюстрируют это сходство.

1°. Отношение сравнения является отношением эквивалентности:

a ≡ a (mod m)

a ≡ b (mod m) b ≡ a (mod m)

a ≡ b (mod m), b ≡ c (mod m) a ≡ c (mod m)

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

1. Рефлексивно очевидна, т.к. a—a делиться на m.

2. Симметричность не менее ясна: если a—b делиться на m, то

b— a тоже делится на m.

3. Транзитивность следует из равенства и свойств делимости.

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

если a ≡ b (mod m), c ≡ d (mod m), то

a + c =b + d (mod m)

a — c =b – d (mod m)

a · c =b · d (mod m)

Доказательство: Пусть , , где и — целые. Тогда

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

Пример:

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

если a ≡ b (mod m), то

a + k ≡ b + k (mod m), kZ,

a · k ≡b · k (mod m), kZ,

(mod m), kN.

Доказательство: Требуемые утверждения легко получить, применяя свойство 2° к сравнениям a ≡ b (mod m) и

k ≡ k (mod m).

Пример: 9 ≡ 4 (mod 5). Для k = 2 получим верные сравнения:

11 ≡ 6 (mod 5), 18 ≡ 8 (mod 5), 81 ≡ 16 (mod 5).

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

a + b ≡ с (mod m) a ≡ c-b (mod m)

Доказательство: Следует из свойства 3° при k = —b.

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

5°. В любой части сравнения можно добавить или отбросить слагаемое, кратное модулю:

a ≡ b (mod m) a + m · k ≡ b (mod m)

Доказательство: По определению сравнимости:

m · k ≡ 0 (mod m). Складывая это сравнение с данным сравнением

a ≡ b (mod m) получим требуемое. Для доказательства обратного утверждения используем операцию вычитания.

Пример: Свойство 5° используют при подсчете дней недели:

3 ≡ b (mod 7) 24 ≡ b (mod 7).

Если 3 числа были вторник, то 24 числа тоже будет вторник.

6°. Обе части сравнения можно сократить на их общий множитель, если он взаимно прост с m:

если a · k ≡ b · k (mod m) и при этом НОД(k,m) = 1,

то a ≡ b (mod m).

Доказательство: Пусть a · k — b · k делится на m. По условию

k и m взаимно простые a—b делиться на m a ≡ b (mod m).

Замечание: Условие взаимной простоты k и m очень важно. Вообще говоря, сокращение может привести к неверному результату. Например, 8 ≡ 6 (mod 2), но 4 3 (mod 2). Впрочем, иногда после сокращения на k результат может оказаться верным, хотя k и m не взаимно просты:

Например, 85 ≡ 10 (mod 15).

После сокращения на 5 получим верное сравнение

17 ≡ 2 (mod 15).

Рассмотренные свойства сравнений обобщаются следующее теоремой.

Теорема 2: Пусть — с целыми коэффициентами. Пусть x ≡ y (mod m).

Тогда p(x) ≡ p(y) (mod m).

Если, кроме того, (mod m), i = 0,1,2…n, то

(mod m).

Доказательство: Непосредственно следует из свойств 2° и 3°.

Замечание 1: Аналогичная теорема верна и для многочленов от n переменных с целыми коэффициентами. Например,

если (mod m), i =1,2,3…n, то

(mod m).

Замечание 2: Встречающиеся в сравнении показатели степеней, нельзя заменять сравнимыми по модулю m. Иначе говоря, из того, что n ≡ k (mod m) не следует, что

(mod m). Например, 3 ≡ 8 (mod 5), но (mod 5), так как (mod 5), а (mod 5).

В свойствах 7° — 10° некоторые манипуляции проводят не только с обеими частями сравнения, но и с модулем m.

7°. Обе части сравнения и модуль можно домножить или сократить на их общий множитель:

a ≡ b (mod m) a · k ≡ b · k (mod mk)

Доказательство: Пусть a ≡ b (mod m). Тогда a = b + m∙t a∙k = b∙k + m∙k∙t a∙k ≡ b∙k (mod mk).

Эти же рассуждения можно провести в обратном порядке.

8°. Если два числа сравнимы по модулю m, то они сравнимы по любому модулю d, делителю числа m:

.

Доказательство: Если a—b делиться на m, а m делиться на d, то по транзитивности a—b делиться d a ≡ b (mod d).

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

,

где .

Доказательство: Если , то разность a—b делиться на и на . Значит, (свойство 1 НОК) a—b делиться на , т.е. a ≡ b (mod m). Такое же рассуждение сохраняет силу и для нескольких модулей.

10°. Если a ≡ b (mod m), то множество общих делителей a и m совпадает с множеством общих делителей b и m. В частности НОД(a,m) = НОД(b,m).

Доказательство: Пусть a ≡ b (mod m). Тогда a – b = m∙t.Если d — общий делитель a и m, то — общий делитель b и m. Обратное аналогично.

п.2 Простейшие применения сравнений

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

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

Решение: Имеем сравнение 2012 ≡ 612 ≡ -18 ≡ 3 (mod 7). Значит,

(mod 7)

Но , поэтому

Ответ: остаток равен 3.

Пример 2: Доказать, что делится на 17 при всех .

Решение: Воспользуемся тем, что 258 (mod 17). Имеем

Следовательно, данная сумма делится на 17.

Пример 3: Вывести признаки делимости на 9 и на 11.

Решение: Любое натурально число N можно записать в виде

Заметим, что 10 ≡ 1 (mod 9). Следовательно,

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

|| N делится на 9 сумма цифр числа N делится на 9||

Аналогично, из сравнения 10 ≡ -1 (mod 11) следует, что

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

N делится на 11Разность между суммой цифр числа N, стоящих на нечетных местах и суммой цифр, стоящих на четных местах, делится на 11.

Пример 4: Доказать, что уравнение не имеет решений в целых числах.

Решение: Любое решение x должно удовлетворять сравнению

При делении на 5 число x может иметь в остатке 0,1,2,3 и 4.

значит не может иметь остаток 3, т.е. сравнение не имеет решений.

Пример 5: Определить день недели по заданной дате.

Решение: Пусть N обозначает год, m — месяц, d — день

(1≤ m≤12), (1≤ d≤31) Первым месяцем года (m = 1) будем считать март, вторым (m =2) — апрель и т.д. Тогда в високосные годы день 29 февраля добавляется в конце года, что удобно для расчета.

Обозначим ω — номер для недели (1≤ ω≤ 7), начиная отсчет с понедельника:

ω = 1 — Пн, ω = 2 — Вт, ω = 3 — Ср ,…, ω=7 —Вс.

Пусть — номер того дня недели, который мы примем за точку отсчета. Напомним, что Россия перешла на григорианский календарь в феврале 1918 года, поэтому примем в качестве день недели 1 марта 1920 года. Таким образом, считаем

Пусть — номер дня 1 марта N-го года. Заметим, что

365 ≡ 1 (mod 7), поэтому каждый невисокосный год номер дня недели увеличивается на 1. Если же прошлый год был високосным, то к номеру дня недели добавим 2, т.к.

366 ≡ 2 (mod 7). Следовательно,

(mod 7)

Упростив это выражение, получим

(mod 7),

(mod 7).

Вычислим . 1 марта 2012 года приходится на четверг, т.е. отсюда следует, что

(mod 7),

(mod 7).

Итак, 1 марта 1920 года был понедельник, следовательно,

(mod 7). (1)

Пусть теперь задано число d месяца m года N. Чтобы определить искомый день недели осталось вычислить количество дней, прошедших от 1 марта до заданной даты. Вычислим сначала номер дней недели для 1 числа каждого месяца.

В марте 31 день 1 апреля имеет номер (mod 7)

В апреле 30 дней 1 мая имеет номер (mod 7)

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

Номер возрастает примерно на в месяц. Поэтому нетрудно подобрать формулу

m = 1,2,3…,12

которая дает нужное добавочное слагаемое для любого месяца.

Итак, если ω — искомый день недели d числа m месяца N года, то к формуле (1) нужно прибавить и (d-1) — количество дней от 1 числа до нужной даты. В итоге получим

(mod 7)

Определим, для примера день недели 22 июня 1941 года. Имеем N = 1941, m = 4, d = 22.

Сравнение целых чисел по модулю

Каждому целому числу отвечает определенный остаток от деления его на т (теорема 3).

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

Сравнимость чисел а и b по модулю т записывается так:

• 45. Сравнимость чисел aub по модулю т равносильна:
• 1) возможности представить а в виде а = b+mt, где t — целое;
• 2) делимости а- b на т.

Действительно, из a=b(mod т) следует откуда

Обратно, из а = b+mt, представляя b в виде

выводим

т.е.

Поэтому верно утверждение 1.

Из 1 непосредственно следует утверждение 2

Свойства сравнений, подобные свойствам равенств

46. Два числа, сравнимые с третьим, сравнимы между собою.

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

Тогда (из 45)

откуда или (из 45)

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

К каждой части сравнения можно прибавить любое число, кратное модуля. Действительно, складывая сравнение a=b с очевидным сравнением mk=0(mod), получим a+mk=b(mod т).

48. Сравнения можно почленно перемножать.

Действительно, рассмотрим снова сравнения (1) и вытекающие из них равенства (2). Перемножая почленно равенства (2), получим

где N — целое. Следовательно (1, с, § 1),

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

Действительно, перемножив сравнение a=b(mod т) с очевидным сравнением k=&(mod т), получим ak=bk (mod m).

49. Свойства 47 и 48 (сложение и умножение сравнений) обобщаются следующей теоремой.

Если в выражении многочлена с целыми коэффициентами S= ^ Aa_t, . a_kx“’ . х“ 1 заменим Аа,, . a_k, X_k Числами Ba_v . a_k, У₁.—, у_k, сравнимыми с прежними по модулю т, то новое выражение S будет сравнимо с прежним по модулю т.

откуда, суммируя, получим Если

a=b(mod m), а, = b, (mod m), . а_л = b„ (mod m), x=x,(mod m), то

ах» + а_|х» _1 +. + а_п = bx» + b,x» _1 +. + b„(mod m).

Это утверждение есть частный случай предыдущего.

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

Действительно, из a=b(mod т), а=а, d, b= b,d, (d, m)=l следует, что разность а-b, равная (а, —b,)d, делится на т. Поэтому (из 11) а,-Ь, делится на ш, т.е. а, = b,(mod m).

Особые свойства сравнений

51. Обе части сравнения и модуль можно умножить на одно и то же целое. Действительно, из a=b(mod т) следует:

и, следовательно, ак = bk(mod тк).

52. Обе части сравнения и модуль можно разделить на любой их общий делитель.

Действительно, пусть Имеем

и, следовательно, aj = b, (mod т,).

53. Если сравнение а = b имеет место по нескольким модулям, то оно имеет место и по модулю, равному общему наименьшему кратному этих модулей.

В самом деле, из a=b(mod m,), a=b(mod m₂), . a=b(mod m_k) следует, что разность a-b делится на все модули т_<, т₂. т_к. Поэтому (из 29) она должна делиться и на общее наименьшее кратное т этих модулей, т.е. а = b( mod).

54. Если сравнение имеет место по модулю т, то оно имеет место и по модулю d, равному любому делителю числа т.

В самом дело, из а = b(mod т) следует, что разность а — b должна делиться на т; поэтому (из 1) она должна делиться на любой делитель d числа т, т.е. а = b( mod d).

55. Если одна часть сравнения и модуль делятся на какое-либо число, то и другая часть сравнения должна делиться на то же число.

Действительно, из а = b(mod т) следует а = b + mt; если ант кратны d, то (из теоремы 2) и b должно быть кратным d, что и утверждалось.

56. Если а = 6(mod m), то (а, т)= (b, т).

Действительно, ввиду теоремы 2 это равенство непосредственно следует из а = b + mt.

Полная система вычетов

57. Числа равноостаточные, или, что то же самое, сравнимые но модулю т, образуют класс чисел по модулю т.

Из такого определения следует, что всем числам класса отвечает один и тот же остаток г, и мы получим все числа класса, если в форме mq+r заставим q пробегать все целые числа.

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

58. Любое число класса называется вычетом по модулю т по отношению ко всем числам того же класса. Вычет, получаемый при q = 0, равный самому остатку г, называется наименьшим неотрицательным вычетом.

Вычет р, самый малый по абсолютной величине, называется абсолютно наименьшим вы четом.

Очевидно при r «f — имеем р =г — т; наконец, если т

, то за р можно принять любое из двух чисел 2 и 2 — m = — 2 •

Взяв от каждого класса по одному вычету, получим полную систему вычетов по модулю т. Чаще всего в качестве полной системы вычетов употребляют наименьшие неотрицательные вычеты 0, 1. ш — 1 или также абсолютно наименьшие вычеты; последние, как это следует из вышеизложенного, в случае нечетною т представляются рядом

а в случае четного т каким-либо из двух рядов:

59. Любые т чисел, попарно несравнимые по модулю т, образуют полную систему вычетов по этому модулю.

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

60. Если (а, т)=1 и х пробегает полную систему вычетов по модулю т, то ах+b, где b -любое целое, тоже пробегает полную систему вычетов по модулю т.

Действительно, чисел ах+b будет столько же, сколько и чисел х, т.е. т. Согласно с остается, следовательно, только показать, что любые два числа ах, +Ь и ах₂ +Ь, отвечающие несравнимым х, и х₂, будут сами несравнимы по модулю т.

Но допустив, что ях, +b = ах, +b(mod т), мы придем к сравнению ах, = ах ₂ (mod т), откуда, вследствие (а, т)=1, получим х, = х₂ (mod т), что противоречит предположению о несравнимости чисел х, и х,.

Приведенная система вычетов

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

Взяв от каждого такого класса по одному вычету, получим приведенную систему вычетов по модулю т. Приведенную систему вычетов, следовательно, можно составить из чисел полной системы, взаимно простых с модулем. Обыкновенно приведенную систему вычетов выделяют из системы наименьших неотрицательных вычетов: 0, 1, . т-1. Так как среди этих чисел число взаимно простых с т есть 1 и (а, т) = 1 имеем (теорема Эйлера):

Действительно, если х пробегает приведенную систему вычетов

составленную из наименьших неотрицательных вычетов, то наименьшие отрицательные вычеты р_х, р₂, . р_с чисел ах будут пробегать ту же систему, но расположенную, вообще говоря, в ином порядке (согласно 63).

Перемножая почленно сравнения

откуда, деля обе части на произведение г, г₂.. .г₍ = р_хр₂ . р_с, получим а’ =1 (mod т).

65. При р простом и а, не делящимся на р, имеем (теорема Ферма):

Эта теорема является следствием теоремы 64 при т=р. Последней теореме можно придать более удобную форму. Именно, умножая обе части сравнения (1) на а, получим сравнение:

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

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

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

Пример: 32 и 39 сравнимы по модулю 7, так как 32 = 7∙4 + 4, 39 = 7∙5 + 4.

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

System idle process что это

Theme hospital как установить русификатор

Как узнать dpi изображения

Что поставить на рабочий стол