No Image

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

1 просмотров
11 марта 2020

Определение 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).
Читайте также:  1С 8 отчет с группировками

где 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. Все свойства сравнений остаются в силе и для отрицательных модулей.

Так, 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 без остатка.

    С ужасом обнаружил, что на пикабу нет статьи про такую прекрасную вещь, как сравнения по модулю и их применение в решении задач на делимость. А тем временем школьники страдают от сложности задачи "Найти, при каких натуральных n выражение n^4 + n^3 + n^2 + 2 делится на 4 без остатка или показать, что таких нет". Вне всяких сомнений особо шустрые школьники решат эту задачу, но сколько на это уйдёт времени? Я же предлагаю использовать метод сравнений по модулю, который в сущности своей довольно прост. В конце мы режим и эту задачу. Кстати, кажется, он может пригодиться даже на ЕГЭ. Итак.

    Вспомним несколько простых фактов о делимости в Z. Собственно, иную и не рассматриваем. Поделить a на b (условимся рассматривать только целые числа) означает представить a как

    Дубликаты не найдены

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

    А что Вам непонятно?

    А ещё я решил в 4-м примере не ту задачу. Но не суть. Решённая (почти) даже посложнее.

    Очень познавательно! А вот нас почему-то ни в школе ни в институте этому никто не учил.

    эээээ поясни вот какой момент:

    ты хочешь доказать a^n + b^n ≡ 0 (mod a – b), но у тебя доказывается, что

    a^n – b^n ≡ 0 (mod a – b)

    Это как? Банальный пример. a=5, b=2, n=2, (25+4)%3=29%3=2. А вот (25-4)%(5-2)=0.

    Привет" хочу рассказать всем, так вопрос". А почему убрали а, 1 степени, так как большинство случаев, n или к, с лёгкостью делилась так же"; бы на 4, пока..

    Они, видимо, говорят про то, что числа (a^n + b^n) и (a^n b^n) разные.
    В задаче требуется доказать:

    а в вашем доказательстве все сводится к

    a^n b^n ≡ 0 (mod a – b)

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

    Поставил плюс, как только прочитал первое предложение :)))

    физ-мат фак.сразу вспомнил.

    О сообществе

    Мы любим науку и популяризируем её! Мы — лига науки Пикабу!

    Основные условия публикации

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

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

    – Научные статьи должны сопровождаться описанием исследования, доступным на популярном уровне. Слишком профессиональный материал может быть отклонён.

    – Видеоматериалы должны иметь описание.

    – Названия должны отражать суть исследования.

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

    Не принимаются к публикации

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

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

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

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

    – Попытки использовать сообщество для рекламы.

    – Многократные попытки публикации материалов, не удовлетворяющих правилам.

    – Нарушение правил сайта в целом.

    Окончательное решение по соответствию поста или комментария правилам принимается модерацией сообщества. Просьбы о разбане и жалобы на модерацию принимает администратор сообщества. Жалобы на администратора принимает @SupportComunity и общество пикабу.

    Комментировать
    1 просмотров
    Комментариев нет, будьте первым кто его оставит

    Это интересно
    No Image Компьютеры
    0 комментариев
    No Image Компьютеры
    0 комментариев
    No Image Компьютеры
    0 комментариев
    No Image Компьютеры
    0 комментариев
    Adblock detector