Система остаточных классов: различия между версиями

'''Система остаточных классов (СОК)''' (от {{lang-en|Residue number system}}, другое название '''Модулярная арифметика''') — [[Система счисления|непозиционная система счисления]]. Представление числа в системе остаточных классов основано на понятии [[Сравнение по модулю|вычета]] и [[Китайская теорема об остатках|Китайскойкитайской теореме об остатках]]. СОК определяется набором попарно [[Взаимно простые числа|взаимно простых]] ''модулей'' <math>(m_1,\, m_2,\, \dots,\, m_n)</math>, т.е.то есть таких, что [[Наибольший общий делитель|<math>\gcd(m_i,\, m_j)=1</math>]] <math>(i,\, j=0,\, 1,\, \dots,\, n;\ i\neq j)</math>, называемых базисом, с произведением <math>M=m_1\cdot m_2\cdot \dots\cdot m_n,</math> так, что каждому целому числу <math>x</math> из отрезка <math>[0,\ M-1]</math> ставится в соответствие набор вычетов <math>(x_1,\, x_2,\, \dots,\, x_n)</math>, где

При этом [[Китайская теорема об остатках|Китайскаякитайская теорема об остатках]] гарантирует однозначность (единственность) представления целых неотрицательных чисел из отрезка <math>[0,\ M-1]</math>.

=== Пример деления, при условии, что оновозможно делитсяделение нацело ===

Это и есть правильный результат — число 208. Однако такой результат можно получить, только если известно, что деление производится без остатка.

* [http://bigenc.ru/mathematics/text/3954960 Статья "Модулярная арифметика" в большойБольшой российскойРоссийской энциклопедииЭнциклопедии]