2014-02-04
1241
Конгруэнтные процедуры представляют собой арифметические операции, в основе которых лежит фундаментальное понятие конгруэнтности.
Два целых числа α и β конгруэнтны или сравнимы по модулю m, m – целое число, тогда и только тогда, когда существует такое целое число k, что α – β = km, т.е. разность α – β делится на m, и числа α и β дают одинаковые остатки от деления на абсолютную величину числа m.
Конгруэнтные процедуры являются чисто детерминированными, так как описываются в виде рекуррентного соотношения (8.3), и имеют вид.
, (8.4)
где 
, l, m, M – неотрицательные целые числа.
Раскроем рекуррентное соотношение (8.4):
(8.5)
Если заданы начальные числа X 0, l, m, M (8.5) последовательность целых чисел { Xi }, составленную из остатков от деления на М членов последовательности 
.
Таким образом, для любого 
справедливо неравенство 
, получится последовательность рациональных чисел из единичного интервала (0, 1) 
.
