Презентация, доклад по теме Теория сравнений

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

целого а
(а є Z) существует единственная пара целых
чисел q и r, таких, что a=mq+r, 0≤ r< m. (По
теореме о делении с остатком).
Определение 1. Если два целых числа a и b при
делении на целое положительное число m
дают один и тот же остаток r, так, что
a=mq1+r и b=b=rq2+r, 0≤rто они называются сравнимыми по модулю m.

а≡b (mod m)
”а сравнимо с b по модулю m”.
Определение 2. Соотношение а≡b (mod m)
называется сравнением.

же остаток 2,
следовательно, они сравнимы по модулю 5:
57≡37(mod 5).
2. 25 при делении на 3 дает остаток 1:
25:3=8 (rest 1);
  35 при делении на 3 даёт остаток 2:
35:3=11 (rest 2);
 Значит, эти числа несравнимы по модулю 3:
25≡33 (mod 3).

рефлексивно, симметрично и транзитивно.
a≡a (mod m);
a≡b (mod m)  b≡a (mod m);
(a≡b (modm), b≡c (modm)) => (a≡c(modm)).

вычитать и перемножать:
a1≡b1(mod m) a2≡b2(mod m)
а1±a2≡b1±b2 (mod m)
  а1a2≡b1b2 (mod m)
Следствие 1. слагаемое из одной части
сравнения перенесли в другую. 
Следствие 2: Сравнение по mod m можно возводить в
натуральную степень, т.е. из a≡b(modm) следует
an≡bn(mod m). 
Следствие 3. Обе части сравнения можно умножать на одно и то же число, т.е. из a≡b(mod m) следует, что ak≡bk(mod m). 
 

обе части сравнения, сохраняя при этом данный модуль.
4. Обе части сравнения и модуль можно умножать на любое d є Z, а также делить на любой их общий делитель, больший нуля, т.е.
(a≡b (mod m)) => (ad≡bd (mod md)).

место по модулю, равному HОK этих модулей.
a≡b (mod m1)
a≡b (mod HOK(m1,m2))
a≡b (mod m2)

целые числа, которые
при делении на m дают один и тот же
остаток r, в один класс, обозначив его
через Cr.
Тогда в зависимости от возможных m остатков
0,1,2,…,m-1 при делении на m все целые числа
разбиваются на m классов:
С0, С1, С2,…,Сm-1, которые называются классами
вычетов по модулю m.

все можно получить, подставив вместо q
целые числа.
Например, по модулю 10 все числа, дающие
остаток 3, имеют вид 10q+3, qєZ.
…; 7;-17; -7; 3; 13; 23…
Числа сравнимы по модулю m тогда и только тогда, когда они принадлежат одному и тому же классу по модулю m.
Определение 4. Числа одного и того же класса называются вычетами этого класса.

классу Ck+l;
b) Если k+l≥m, то полученное число принадлежит классу Ck+l-m
 
2. Произведение вычетов.
Поделим k*l на m и получим остаток r, т.е. kl=mq+r
Произведение принадлежит классу Cr.
 

С4 в сумме
всегда дают вычет из класса С7, а в
произведении вычет их класса С3*4-10=С2.
13+24=37 -27+24=-13
13*24=312 -27*14=-378
При помощи сравнений можно записать так:
13≡ 3(mod 10) 37≡ 7(mod 7)

24≡4mod 10) 312≡ 2 (mod 2)
 

взять по одному представителю, то полученную систему чисел называют полной системой вычетов по модулю m.
Например, чтобы составить полную систему
вычетов по модулю 10, мы должны взять по
одному представителю из классов, числа
которых записываются в следующем виде:
10q+0, 10q+1, 10q+2 … 10q+9.
20, 31, 112,…, 39.

полной системе наименьших неотрицательных вычетов.
В таком случае вычеты равны остаткам r, и
полная система вычетов имеет вид
0, 1, 2, … ,m-1.
Пример.
Составить полную систему наименьших
неотрицательных вычетов по модулю 10.

m.
Пример.
Составить полную систему наименьших
по абсолютной величине вычетов по модулю
10.

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

вычетов, в
приведённой системе, по модулю m решается
при помощи функции Эйлера μ(m). Эта
функция определяется для всех целых
положительных m как число целых
положительных чисел, не превосходящих m и
взаимно простых с m. В приведённой системе
вычетов по модулю m имеется как раз μ(m)
чисел.

на 7 одинаковые остатки. (проверить!);
б) при делении на 8 число 53 дает остаток 5;
г) определить остаток r от деления 73 на 8.
 
2. Записать с помощью сравнений:
а) числа n – четные;
б) числа n – нечетные;
в) n = 5к + 3;
г) n = 7к – 2.

а) а = 11·18·13·19·2322 по модулю 7?
б) а = 12·17·18·21·23·2412 (mod 5)
в) а = 9·10·11·121·242 (mod 9).
4. Найти остаток от деления f(75) на 11, если f(х) = х10 + 4х7– 22х4 + 101.
5. Составить по модулям 14 и 15 полные и
приведенные системы наименьших
неотрицательных, наименьших
положительных и абсолютно наименьших
вычетов.