В лекциях были даны основные определения, связанные со сравнимыми числами, классами вычетов, в текущем материале приведены несколько примеров решения задач, которые не были рассмотрены в теоретической части.
Сравнения первой степени с одним неизвестным ax ≡ b (mod m).
Решите уравнение 1287x ≡ 447 (mod 516) - обозначим через (1).
Решение:
1) Заменим коэффициенты уравнения соответствующими наименьшими положительными вычетами по модулю 516, получим:
255x ≡ 447 (mod 516) - обозначим через (2).
2) Если наибольший общий делитель (a, m) чисел a и m равен d и d делит b, то сравнение ax ≡ b (mod m) имеет d решений.
Если же d не делит b, то сравнение ax ≡ b (mod m) не имеет решений.
Для уравнения 255x ≡ 447 (mod 516) имеем d = (a, m) = (255, 516) = 3. Поскольку d = 3 делит b = 447, то уравнение 255x ≡ 447 (mod 516), а, следовательно, и уравнение 1287x ≡ 447 (mod 516) имеет 3 решения.
3) Разделим обе части уравнения 255x ≡ 447 (mod 516) и его модуль на d = 3, получим: 85x ≡ 149 (mod 172).
Рассмотрим два способа решения сравнения ax ≡ b (mod m), где (a, m) = 1.
Первый способ решения сравнения ax ≡ b (mod m), где (a, m) = 1.
Второй способ решения сравнения ax ≡ b (mod m), где (a, m) = 1.
Третий способ решения сравнения ax ≡ b (mod m), где (a, m) = 1.
В вопросно-ответную систему Wolfram|Alpha внесем следующую команду:
1287x ≡ 447 (mod 516)
Получим результат:
В результате показано решение (см. Solution in the least residue system).
В качестве Упражнения попробуйте решить всеми указанными способами следующие сравнения ax ≡ b (mod m) по модулю (или покажите, что решение на множестве целых чисел отсутствует).
Рекомендуется для начала проверить наличие решения в вопросно-ответной системе Wolfram|Alpha. Пример для 30-ого варианта:
Вводим команду
253x ≡ 182 (mod 61)
получаем результат: