|
Подскажите, пожалуйста, как решить данное сравнение и вообще можно ли, не используя непрерывные дроби или Эйлера. То есть обычными преобразованиями (делением на взаимно пр. с модулем; +/-/* на кратное модулю).
задан 4 Ноя '14 2:08 
Andrew |
|
Да, конечно, здесь всё именно так и решается, поскольку это линейное сравнение. Частное $%1153/7$% близко к $%165$%, поэтому домножаем на этот коэффициент. Он взаимно прост с модулем, что легко проверить. Получается $%2x\equiv1155x\equiv3795\equiv336\pmod{1153}$%, откуда после сокращения на $%2$% будет $%x\equiv168\pmod{1153}$%. отвечен 4 Ноя '14 2:22 
falcao Да, ответ правильный. Вот только я не совсем понял, почему мы можем в начале домножить на 165. Я просто читал, что можно только делить на взаимно простое с модулем. А вот домножить (или +-) можно на число, кратное модулю.
(4 Ноя '14 15:39)
Andrew
@Andrew: возможность домножения сравнения на целый коэффициент -- это более элементарное свойство по сравнению с тем, о котором Вы говорите. Обычно оно упоминается среди простейших свойств сравнений. Имеется в виду, что из $%a\equiv b\pmod m$% следует $%ka\equiv kb\pmod m$%, что очевидно из определения. Обратная же импликация верна не всегда, и здесь нужно свойство взаимной простоты $%k$% и $%m$%. При этом ограничении оба условия становятся равносильными, поэтому такой приём можно свободно использовать при решении сравнений.
(4 Ноя '14 15:45)
falcao
(продолжение) Равносильность условий $%a\equiv b\pmod m$% и $%ka\equiv kb\pmod{km}$% для любого натурального $%k$% (без ограничений) -- это ещё одно верное свойство, и оно иногда используется, но в данном случае оно не нужно.
(4 Ноя '14 15:47)
falcao
Все понял, спасибо.
(4 Ноя '14 17:10)
Andrew
|