вопрос по алгебре: решение сравнений по модулю

[tavrik]

как решаются сравнения с модулями. в целых числах.
я их до этого не встречал нигде.

например:
$14x\equiv 5\pmod{45}$

или система из двух уравнений:

1. $3х\equiv 2\pmod {5}$
2. $2x\equiv 1\pmod {3}$
----------------------------------------------
насколько я понял из википедии вначале ищем обратное для 14

[bnovikov]

А дальше умножаем обе части сравнения на это обратное.

[tavrik]

то есть, здесь:
$14^{-1}\equiv 29\pmod{45}$
$x\equiv 10\pmod{45}$

???

а количество решений от чего зависит?
например, если первоначально 45 и 14 имели общие делители больше 1 - число решений увеличилось бы?

спасибо

[bnovikov]

tavrik в сообщении #512020 писал(а):

например, если первоначально 45 и 14 имели общие делители больше 1 - число решений увеличилось бы?

Если 45 и 14 имеют общие делитель, то либо 5 тоже имеет его (тогда все можно сократить), либо не имеет (тогда решения нет).

А вообще-то не ленитесь, откройте любой учебник по теории чисел, там все написано.

[Sonic86]

tavrik в сообщении #512020 писал(а):

а количество решений от чего зависит?

Если сравнение $f(x) \equiv 0 \pmod m$ по модулю $m=p_1^{a_1}\dots p_s^{a_s}$, то $N(f(x) \equiv 0 \pmod m)=N(f(x) \equiv 0 \pmod{p_1^{a_1}}) \cdot \ldots \cdot N(f(x) \equiv 0 \pmod{p_s^{a_s}})$ по китайской теореме об остатках. Далее, чаще всего $N(f(x) \equiv 0 \pmod{p^a})$ вычисляется через $N(f(x) \equiv 0 \pmod{p})$ (если $f$ - многочлен, то эти числа решений попросту равны). Ну и если $f$ - многочлен степени $d$, то $N(f(x) \equiv 0 \pmod{p}) \leqslant d$, так как $\mathbb{Z}_p$ - поле (в поле используем теорему Безу). Это все, если $f(x) \equiv f(x \mod p) \pmod p$ (т.е. для $f(k)=k!$ число решений сравнения считается совсем иначе).

О решениях сравнений можно почитать в Бухштабе - очень простая книжка. О том, как довольно изощренно можно вычислять число решений сравнения (и даже в конечных полях) можно узнать в Айрленде, Роузене

[tavrik]

а более элегантного решения, чем то что я нашел - нет?
в том смысле, что до $14\cdot29$ надо было довольно долго топать.

и еще вопрос:
видел пример, где по пути встречается остаток -1, все возводится в квадрат и тогда в остатке получае единицу.
$a^k\equiv {-1}\pmod b$
$a^{2k}\equiv 1\pmod b$
вопрос, является ли эта степень(2k) наименьшей, при возведении в которую получаем в остатке единицу?
Спасибо.

[VAL]

tavrik в сообщении #512011 писал(а):

как решаются сравнения с модулями. в целых числах.
я их до этого не встречал нигде.

Откройте любой учебник по теории чисел.

Цитата:

например:
$14x\equiv 5\pmod{45}$

или система из двух уравнений:

1. $3х\equiv 2\pmod {5}$
2. $2x\equiv 1\pmod {3}$

Полагаю первое сравнение Вам решить не удастся

Цитата:

----------------------------------------------
насколько я понял из википедии вначале ищем обратное для 14

В общем, да. А вот способы для нахождения обратного могут быть совершенно разные: теорема Эйлера, алгоритм Евклида, метод вспомогательных сравнений, комбинирование преобразований, не нарушающих равносильности. (Все это касается ситуации, когда Вы уже перешли к сравнению, в котором коэффициент при неизвестном и модуль взаимно просты.)

[tavrik]

какое - по модулю 45?
я вроде нашел что 29 это обратное 14 в $Z_{45}$

а, или там где я забыл переменную?
ответ для системы сравнений с одним неизвестным это все равно не одно число а группа чисел...
правильно? или может быть лишь одно чилсо удовлетворяет требованиям?
здесь я нашел что $x=4 в Z_5$ и $x=2 Z_3$, но как оформить?
PS
над х и остатками черточки - так как это не цифры

-- Вс дек 11, 2011 17:14:30 --

какое - по модулю 45?
я вроде нашел что 29 это обратное 14 в $Z_{45}$

а, или там где я забыл переменную?
ответ для системы сравнений с одним неизвестным это все равно не одно число а группа чисел...
правильно? или может быть лишь одно чилсо удовлетворяет требованиям?
здесь я нашел что $x=4 в Z_5$ и $x=2 Z_3$, но как оформить?
PS
над х и остатками черточки - так как это не цифры

[VAL]

tavrik в сообщении #514363 писал(а):

какое - по модулю 45?
я вроде нашел что 29 это обратное 14 в $Z_{45}$

Угу.

Цитата:

а, или там где я забыл переменную?
ответ для системы сравнений с одним неизвестным это все равно не одно число а группа чисел...

Я бы даже сказал, класс (вычетов по модулю).

Цитата:

правильно? или может быть лишь одно чилсо удовлетворяет требованиям?

Не может. (Если модуль отличен от 0.)

Цитата:

здесь я нашел что $x=4 в Z_5$ и $x=2 Z_3$, но как оформить?

Перейдите к модулю 15.

Цитата:

PS
над х и остатками черточки - так как это не цифры

Достаточно (и более информативно писать $x\equiv 4(\mod 5)$. Это, как раз, означает, что иксы заполняют целый бесконечный класс чисел вида $4+5k$.

Цитата:

-- Вс дек 11, 2011 17:14:30 --

какое - по модулю 45?
я вроде нашел что 29 это обратное 14 в $Z_{45}$

а, или там где я забыл переменную?
ответ для системы сравнений с одним неизвестным это все равно не одно число а группа чисел...
правильно? или может быть лишь одно чилсо удовлетворяет требованиям?
здесь я нашел что $x=4 в Z_5$ и $x=2 Z_3$, но как оформить?
PS
над х и остатками черточки - так как это не цифры

А зачем еще раз: Я с первого понял

[tavrik]

да, класс вычетов, это то слово которое я искал.
сэнкс.
к модулю 15 перейду