 Пусть a,b-целые числа, n - натуральное. Рассмотрим сравнение:
ax?b (mod n)
и поставим задачу отыскания всех целочисленных решений этого сравнения. Допустим, что xo-это решение.
ax0=b+nu для некоторого целого u.
Пусть d=(a,n)
Видно, что условие d делит b является необходимым для того, чтобы сравнение имело решения.
Как мы увидим позже, это условие является так же достаточным.
|
