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

[непроверенная версия][непроверенная версия]
Содержимое удалено Содержимое добавлено
→‎Преамбула: оформление
→‎Преамбула: оформление
Строка 1:
'''Система остаточных классов (СОК)''' (от {{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 \dotsldots \cdot m_n,</math> так, что каждому целому числу <math>x</math> из отрезка <math>[0,\ M-1]</math> ставится в соответствие набор вычетов <math>(x_1,\, x_2,\, \dots,\, x_n)</math>, где
: <math>x_1 \equiv x \pmod{m_1};</math>
: <math>x_2 \equiv x \pmod{m_2};</math>