Решение линейных сравнений в целых числах

Рассмотрим сравнение вида

ax º b (mod m), (1.7.1)

где a, b Î Z, m Î N, х – искомое значение в Z.

1. Пусть (a, m) = 1. Тогда (1.7.1) имеет в качестве множества решений – единственный класс вычетов по модулю m. По теореме 1.7.1 – обратимый класс в Z / m Z. – единственный обратный класс к . В Z / m Z сравнение (1.7.1) соответствует уравнению . Умножим обе его части на , получим . = { x + mq | q Î Z } – множество решений (1.7.1). можно найти из соотношения Безу для 1 и чисел a и m, или согласно следствию из теоремы 1.7.3

2. Пусть (a, m) = d > 1 и , тогда (1.7.1) не имеет решений в Z, поскольку не выполняется свойство 6 делимости целых чисел: ax = b + mq, q Î Z, d | a, d | m, но .

3. Пусть (a, m) = d > 1 и d | b. Тогда разделим обе части (1.7.1) и m на d согласно свойству 5 сравнений. Получим сравнение

a ₁ x º b ₁ (mod m ₁), (1.7.2)

где a ₁ = a / d, b ₁ = b / d, m ₁ = m / d, и (a ₁, m ₁) = 1 по свойству 1 взаимно простых чисел. (1.7.2) имеет в качестве множества решений единственный класс вычетов по модулю m ₁ согласно случаю 1. Числа из = { x ₀ + m ₁ q | q Î Z } являются решениями (1.7.1), так как a (x ₀ + m ₁ q) = da ₁ x ₀ + ma ₁ q º db ₁ + dm ₁ t ₀ º b (mod m) для " q Î Z и фиксированного t ₀ Î Z. Какие еще возможны решения (1.7.1)? Пусть – решение (1.7.1), тогда . Это возможно тогда, когда Û m | ay Û m ₁ | a ₁ y Þ m ₁ | y по свойству 2 взаимно простых чисел, значит, . С другой стороны, для таких значений y любое является решением сравнения (1.7.1). Итак, по модулю m – все множества решений (1.7.1).

Дата добавления: 2014-01-05