Система остаточных классов - введение — различия между версиями
Isaeva (обсуждение | вклад) |
Isaeva (обсуждение | вклад) |
||
| Строка 41: | Строка 41: | ||
== Теорема о делении с остатком. Алгоритм Евклида == | == Теорема о делении с остатком. Алгоритм Евклида == | ||
| − | Теорема | + | '''Теорема о делении с остатком''' |
| − | <math> | + | для любых целых ''a'' и ''b'', |
| + | <math>b \not= 0</math>, существует единственный набор целых чисел ''q'' и ''r'', что a = bq + r и <math>0 \le r < |b|</math>, где |''b''| — модуль числа ''b''. | ||
На этой операции основан алгоритм Евклида нахождения наибольшего общего делителя двух целых чисел. | На этой операции основан алгоритм Евклида нахождения наибольшего общего делителя двух целых чисел. | ||
| + | |||
| + | '''Алгоритм Евклида для целых чисел''' | ||
| + | |||
| + | Пусть <math>a</math> и <math>b</math> — целые числа, не равные одновременно нулю, и последовательность чисел | ||
| + | : <math> a > b > r_1 > r_2 > r_3 > r_4 > \cdots >r_n</math> | ||
| + | определена тем, что каждое <math>r_k</math> — это остаток от деления предпредыдущего числа на предыдущее, а предпоследнее делится на последнее нацело, то есть | ||
| + | : <math>a = bq_0 + r_1</math> | ||
| + | : <math>b = r_1q_1 + r_2</math> | ||
| + | : <math>r_1 = r_2q_2 + r_3</math> | ||
| + | |||
| + | : <math>\cdots</math> | ||
| + | : <math>r_{k-2} = r_{k-1} q_{k-1} + r_k</math> | ||
| + | |||
| + | : <math>\cdots</math> | ||
| + | : <math>r_{n-2} = r_{n-1}q_{n-1}+ r_n</math> | ||
| + | : <math>r_{n-1} = r_n q_n</math> | ||
| + | |||
| + | Тогда НОД(''a'',''b''), наибольший общий делитель <math>a</math> и <math>b</math>, равен | ||
| + | <math>r_n</math>, последнему ненулевому члену этой последовательности. | ||
| + | |||
| + | '''Существование''' таких <math>r_1, r_2, ...</math>, то есть возможность деления с остатком <math>a</math> на <math>b</math> для любого целого <math>a</math> и целого <math>b\ne 0</math>, доказывается индукцией. | ||
| + | |||
| + | '''Корректность''' этого алгоритма вытекает из следующих двух утверждений: | ||
| + | * Пусть <math>a = bq + r</math>, тогда НОД (<math>a</math>, <math>b</math>) = НОД (<math>b</math>, <math>r</math>). | ||
| + | * НОД(0,<math>r</math>) = <math>r</math> для любого ненулевого <math>r</math> (так как 0 делится на любое целое число, кроме нуля). | ||
| + | |||
== Китайская теорема об остатках == | == Китайская теорема об остатках == | ||
Версия 14:16, 26 августа 2014
Содержание
Теоретико-числовая база построения системы остаточных классов
Напомним определение деления с остатком.
Определение. Говорят, что целое число 
делится на натуральное число 
с остатком, если имеется пара целых чисел 
и 
, таких, что 
и 
.
называется делимым, - делителем, - неполным частным, - остатком.
Для целых чисел:
Определение. Говорят, что целое число 
делится на натуральное число 
с остатком, если имеется пара целых чисел и , таких, что и 
.
Пример: 48 при делении на 5 даёт остаток 3, т.к. 
, 
, -48 при делении на 5 даёт остаток 2, т.к. 
, 
.
Сравнения и их основные свойства
Возьмём произвольное фиксированное натуральное число и будем рассматривать остатки при делении на различных целых чисел.
При рассмотрении свойств этих остатков и проведении операций над ними удобно ввести понятие сравнения по модулю.
Определение. Два целых числа 
и 
называются сравнимыми по модулю m, если их разность Невозможно разобрать выражение (лексическая ошибка): a − b
делится без остатка на
Символически сравнимость записывается в виде формулы (сравнения):
Число называется модулем сравнения.
Эквивалентная формулировка:
Определение. Целые числа и называются сравнимыми по модулю m, если остатки от деления этих чисел на равны.
Отношение сравнимости по модулю обладает свойствами рефлексивности, симметричности и транзитивности, т.е. является отношением эквивалентности.
Отнесём все целые числа, дающие при делении на один и тот же остаток в один класс, поэтому получится различных классов по модулю .
Множество всех чисел сравнимых с по модулю называется классом вычетов по модулю .
Подробнее о свойствах сравнений и классах вычетов смотри Сравнения и их основные свойства
Теорема о делении с остатком. Алгоритм Евклида
Теорема о делении с остатком
для любых целых a и b,
, существует единственный набор целых чисел q и r, что a = bq + r и 
, где |b| — модуль числа b.
На этой операции основан алгоритм Евклида нахождения наибольшего общего делителя двух целых чисел.
Алгоритм Евклида для целых чисел
Пусть и — целые числа, не равные одновременно нулю, и последовательность чисел
определена тем, что каждое 
— это остаток от деления предпредыдущего числа на предыдущее, а предпоследнее делится на последнее нацело, то есть
Тогда НОД(a,b), наибольший общий делитель и , равен
, последнему ненулевому члену этой последовательности.
Существование таких 
, то есть возможность деления с остатком на для любого целого и целого 
, доказывается индукцией.
Корректность этого алгоритма вытекает из следующих двух утверждений:
- Пусть
, тогда НОД (, ) = НОД (, ).
- НОД(0,) = для любого ненулевого (так как 0 делится на любое целое число, кроме нуля).
