Что значит mod в математике

Что значит mod в математике

Два натуральных числа a и b, разность которых кратна натуральному числу m, называются сравнимыми по модулю m: a ≡ b (mod m).

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

В том случае, если число n делится на m, то оно сравнимо с нулем по модулю m: n ≡ 0 (mod m).

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

Отметим, что обе части сравнения не всегда можно сократить на какой-либо множитель. Так, 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.

Читайте также:  Как включить компьютер с usb клавиатуры

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

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

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

Пусть p – простое число, a – натуральное число. Тогда a p – a делится на p: a p ≡ a (mod p).

В частности, если p – простое число, a – натуральное число, взаимно простое с p, то a p – 1 ≡ 1 (mod p).

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

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

Чтобы получить остаток от деления n на m, нужно воспользоваться функцией Mod[n,m]. Наименьший возможный остаток в этом случае равен нулю, а наибольший. Как вы думаете, чему равен наибольший возможный остаток? "Конечно, m-1", — возможно, подумали вы. Ну, что же, я, конечно, приветствую ваши глубокие познания в теории чисел, ибо именно так написано во всех классических учебниках по этой дисциплине, если, конечно, именно в этом месте нет какой-либо досадной опечатки. Но должен вас разочаровать: вы не угадали. Зато, надеюсь, вам будет приятно узнать, что возможности функции Mod значительно шире, чем требуется для решения задач из задачников по классической теории чисел. Дело в том, что аргументы этой функции могут быть не только целыми (это предусмотрено классическими учебниками теории чисел), но и вещественными и даже комплексными! А во множестве вещественных чисел, как вы, надеюсь, еще помните, полно сюрпризов. Но сначала давайте рассмотрим простейший случай целых аргументов.

Ну вот, при делении 7 на 5 остаток равен 2. Просто и понятно, даже в уме можно вычислить. Вот еще один пример.

Тоже в уме, и тоже просто и понятно. Но вот несколько примеров с вещественными числами.

Читайте также:  Магнитола на виндовс или андроид что лучше

Теперь, надеюсь, вы поняли, что множество значений Mod[n,m] не имеет набольшего элемента. Можно лишь утверждать, что при вещественных m и n 0
А вот вид вблизи.

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

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