3.1.1. Модулярная арифметика. Основные определения.

Пусть а и п – натуральные числа. "Разделить число а на число п с остатком" – это значит найти целые числа а и r, удовлетворяющие условию

а = q • п + r, где 0  r < п.

При этом число q называют неполным частным, а r – остат­ком от деления числа а на число п.

Если остаток r равен нулю, то говорят, что число п делит число а, или, по-другому, п является делителем числа а и обозначают п|а.

Наибольшее целое число, делящее одновременно целые числа а и b, называется их наибольшим делителем и обозна­чается НОД(a, b) или просто (а, b). Если (а, b)=1, то а и b на­зываются взаимно простыми числами.