Задача на теорию сравнений

[Unconnected]

Такой пример: $x^{47}+11x^{42}-6x^{19}+4=0 \mod{245}$

Нашёл два решения по модулю 7 и одно по модулю 5. Теперь, я так понимаю, нужно каждое решение по модулю 7 привести к модулю 49 (тогда их станет в 7 раз больше (?)), и уже решать системы из решений по 49 и 5. Но их получается как-то много (14), кажется, что-то не так делаю..

[svv]

(Unconnected)

Простите, а что по этой теме: помог ответ, не помог? Какая-нибудь обратная связь...

[ИСН]

Не помню я всей этой теории, а вот простой пример: $x^2\equiv x\mod 1000$. Ну, там понятно: по модулям 2, 5, потом скрестить, там 4 решения... И знаете что? Их не стаёт больше, когда переходим к следующим степеням.

[Unconnected]

Ну если $x \equiv 2 \mod 7$, то $x \equiv 2,9,16,23,30,37,43 \mod 49$, так ведь..

[bot]

ИСН в сообщении #503916 писал(а):

Их не стаёт больше

Может стать, может не стать, может обломаться. Ровно одно продолжение решения $x_0 \pmod {p^k}$ при подъёме $k\rightarrow k+1$ будет, если в случае $f'(x_0)\not\equiv 0 \pmod p$, в противном случае либо размножение в $p$ экземпляров, либо облом продолжения.
В данном случае по модулю 7 имеем решения 2 и -3. В первом случае производная ненуль и продолжение однозначно, во втором она нуль и стало быть либо размножается: $-3+7k, k=$семь штук подряд, если $f(-3)\equiv 0\pmod{49}$ либо глохнет в противном случае.

-- Вт ноя 15, 2011 10:16:22 --

Unconnected в сообщении #503938 писал(а):

так ведь..

Не так - из них годится ровно одно.

[Unconnected]

Не понял про продолжение.. откуда тут производная вообще?

Решая по модулю 7 получил $x^{2}+x+1 \equiv 0 (mod 7)$. Решения: 1/2 , -3/2, эти дроби привёл к 4 и 2 (прибавив к каждому числителю семёрку, правомерно?).

Цитата:

из них годится ровно одно.

Но проверить ведь нужно все (читай, решить кучу систем)?
Читаю Бухштаба параллельно, вроде чего-то проясняется.. сколько нам, оказывается, недоговаривают)

[bot]

Unconnected в сообщении #504307 писал(а):

откуда тут производная вообще

Не нашли что ли в Бухштабе? Напишу потом - это просто, но сейчас некогда.

Unconnected в сообщении #504307 писал(а):

Но проверить ведь нужно все

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

Upd. Куча систем возникает на завершаещем этапе, когда по китайской теореме об остатках ищем решение по составному модулю. Однако и здесь можно решать одну систему, но с параметрами. Найдя решения останется подставить в него значения параметров, найденные на 1-м этапе.

[Sonic86]

Unconnected в сообщении #504307 писал(а):

Решая по модулю 7 получил $x^{2}+x+1 \equiv 0 (mod 7)$. Решения: 1/2 , -3/2, эти дроби привёл к 4 и 2 (прибавив к каждому числителю семёрку, правомерно?).

Нет. В числителях дробей так прибавлять $7$ нельзя. Вам надо вычислить $2^{-1} \equiv 4 \pmod 7$, поскольку $2 \cdot 4 \equiv 1 \pmod 7$. Сравните полученный ответ с Вашим.

Unconnected в сообщении #504307 писал(а):

Но проверить ведь нужно все (читай, решить кучу систем)?

Решать их все надо за один раз. Посмотрите Боревича, Шафаревича 1-ю главу про $p$-адические числа, авторы там решают сравнение $x^2 \equiv 2 \pmod {7^n}$ для всех $n$ рекуррентно. Вам надо делать так: сначала решаете $f(x) \equiv 0 \pmod p$ где $f$ - целочисленный многочлен, пусть $x_1$ - решение сравнения $f(x) \equiv 0 \pmod p$. Надо найти $x_2$ $f(x_2) \equiv 0 \pmod {p^2}$. Поскольку для также $f(x_2) \equiv 0 \pmod p$, а $f$ - целочисленный многочлен, то $x_2 \equiv x_1 + q_1p \pmod{p^2}$, где $x_1$ дано, а $q_1$ - неизвестное, через которое будем считать $x_2$. Подставляем и получаем линейное уравнение относительно $q_2$ - оттуда его и находим. Коэффициент при $q_2$ будет $f'(x_0)$, поэтому уравнение имеет ровно 1 корень $\Leftrightarrow f'(x_0) \not \equiv 0 \pmod p$ (напишите подстановку в общем виде - увидите производную). И так далее для всех $p^n$ (ну Вам дальше $p^2$ не надобно)

[Батороев]

Пример можно немного упростить, имея в виду то, что $x^{42}\equiv 1;99\pmod {245}$.

[Sonic86]

Батороев в сообщении #504426 писал(а):

Пример можно немного упростить, имея в виду то, что $x^{42}\equiv 1;99\pmod {245}$.

Кстати да, надо было с этого и начинать.

[bot]

Да ну нафиг начинать. Для $m=7^2$ понятна единица, она сама выползет и 99 не при делах, а для $m=5$ овчинка даже и упоминания не стоит, не говоря о выделке. Кстати, откуда 99 вообще нарисовалась? По модулю 5 решения $x\equiv\pm 1$, откуда $x^{42}\equiv 1\not\equiv 99 \pmod 5$ .

-- Ср ноя 16, 2011 18:03:46 --

Не стоит сбивать ТС мелкими брызгами - пусть в главную струю попадёт. Ему поднять надо верно найденные $x\equiv 2, -3\pmod 7$ на уровень $7^2$. Один случай будет с ненулевой производной, а другой наоборот.

Upd. Пока мне некогда было, Sonic86 уже кой-чего выложил (я намеревался больше), может так и лучше - пусть ТС поработает.

[Unconnected]

С многочленами вроде по книжке разобрался, теперь очень интересует, как решать такую башню:
$53^{35^{42^{43}}} \equiv x (\mod 11)$

[Unconnected]

Ааа блин.. и уже не могу отредактировать.
$53^{35^{42^{43}}} \equiv x (\mod 836)$ так правильно.

Sonic, вы, кстати, опечатались наверное в последнем большом сообщении, там сначала $q_1$ было, потом стало $q_2$..

[bot]

КТО Вам поможет и МТФ.

МТФ - малая теорема Ферма
КТО - китайская теорема об остатках

[Sonic86]

Unconnected в сообщении #507609 писал(а):

Sonic, вы, кстати, опечатались наверное в последнем большом сообщении, там сначала $q_1$ было, потом стало $q_2$..

Угу.