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

 

Представление числа в системе остаточных классов основано на понятии [[Сравнение по модулю|вычета]] и [[Китайская теорема об остатках|китайской теореме об остатках]]. СОК определяется набором попарно [[Взаимно простые числа|взаимно простых]] ''модулей'' <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 \ldots \cdot m_n,</math> так, что каждому целому числу <math>x</math> из отрезка <math>[0,\ M-1]</math> ставится в соответствие набор вычетов <math>(x_1,\, x_2,\, \dots,\, x_n)</math>, где