Не делимость

[vorvalm]

(Оффтоп)

Молодец среди овец.

[Shadow]

(Оффтоп)

Боец, вольно.
Задачка достаточно элементарная, чтобы попробовать высунуть голову из жо книжек и решить.

[vorvalm]

(Оффтоп)

Я знаю случай, когда удалили гланды через задний проход,
т.к. у пациента во рту застряла лампочка.

[TOTAL]

Кто-нибудь сформулирует, наконец, теорему из славного Бухштаба, с помощью которой тоже, как оказалось, можно решить задачу?

[nnosipov]

Эта теорема действительно полезна в подобных задачах, вот формулировка.

Теорема. Пусть $p$ делит $f'(a)$ и $x \equiv a \pmod{p^k}$ --- решение сравнения $f(x) \equiv 0 \pmod{p^k}$. 1) Если $p^{k+1}$ не делит $f(a)$, то ни одно из чисел $x \equiv a \pmod{p^k}$ не удовлетворяет сравнению

$$ f(x) \equiv 0 \pmod{p^{k+1}}. \eqno(*) $$

2) Если $p^{k+1}$ делит $f(a)$, то все числа $x \equiv a \pmod{p^k}$ удовлетворяют сравнению $(*)$.

[Deggial]

vorvalm, Shadow, замечание за недопустимые формы ведения дискуссии.

Сообщения свернул в оффтоп.

[TOTAL]

nnosipov в сообщении #663614 писал(а):

Теорема. Пусть $p$ делит $f'(a)$ и $x \equiv a \pmod{p^k}$ --- решение сравнения $f(x) \equiv 0 \pmod{p^k}$.

$x \equiv a \pmod{p^k}$ - какое-то решение или единственное решение?

[nnosipov]

TOTAL в сообщении #663623 писал(а):

$x \equiv a \pmod{p^k}$ - какое-то решение или единственное решение?

Какое-то, ведь их может быть несколько (я имею в виду эти $a$).

[TOTAL]

nnosipov в сообщении #663636 писал(а):

TOTAL в сообщении #663623 писал(а):

$x \equiv a \pmod{p^k}$ - какое-то решение или единственное решение?

Какое-то, ведь их может быть несколько (я имею в виду эти $a$).

Я все должен найти и проверить или только одно любое? Как решать задачу с помощью этой теоремы?

[nnosipov]

TOTAL в сообщении #663651 писал(а):

Я все должен найти и проверить или только одно любое?

Допустим, Вы хотите решить сравнение $f(x) \equiv 0 \pmod{p^{k+1}}$, а все решения $x \equiv a_i \pmod{p^k}$ сравнения $f(x) \equiv 0 \pmod{p^k}$ Вы каким-то образом уже нашли. Теперь для каждого $i$ Вы должны попытаться сконструировать из решения $x \equiv a_i \pmod{p^k}$ сравнения $f(x) \equiv 0 \pmod{p^k}$ одно или несколько решений $x \equiv a_{ij} \pmod{p^{k+1}}$ сравнения $f(x) \equiv 0 \pmod{p^{k+1}}$ (естественно, $a_{ij} \equiv a_i \pmod{p^k}$ для любого $j$). Так вот, Вы всегда сможете сделать это однозначно, если $p$ не делит $f'(a_i)$ (это теорема 158 из Бухштаба). Если же, наоборот, $p$ делит $f'(a_i)$, то либо ничего не получится (см. п. 1) теоремы), либо будет ровно $p$ решений (см. п. 2) теоремы). Итак, пробежавшись по всем $i$, Вы что-то "поднимите" на "следующий этаж", а что-то нет. Если ничего не удастся "поднять", то это будет означать неразрешимость сравнения $f(x) \equiv 0 \pmod{p^{k+1}}$.

В нашем примере $f(x)=x^2+3x+5$, $p=11$, $k=1$. Есть только одно решение $x \equiv 4 \pmod{11}$ сравнения $x^2+3x+5 \equiv 0 \pmod{11}$. Пробуем его "поднять" до какого-нибудь решения по модулю $11^2$, но не получается, ибо $f(4) \not\equiv 0 \pmod{11^2}$. Значит, сравнение $x^2+3x+5 \equiv 0 \pmod{11^2}$ решений не имеет.

[TOTAL]

nnosipov в сообщении #663658 писал(а):

В нашем примере $f(x)=x^2+3x+5$, $p=11$, $k=1$. Есть только одно решение $x \equiv 4 \pmod{11}$ сравнения $x^2+3x+5 \equiv 0 \pmod{11}$. Пробуем его "поднять" до какого-нибудь решения по модулю $11^2$, но не получается, ибо $f(4) \not\equiv 0 \pmod{11^2}$. Значит, сравнение $x^2+3x+5 \equiv 0 \pmod{11^2}$ решений не имеет.

Теперь формулировка теоремы понятна. Но помощь от неё в данной задаче сомнительна.

Вот (бестеоремный ) безтеоремный (как правильно? что-то запутался ) бестеоремный (это моё последнее слово ) подход (разные варианты которого здесь предлагались):

В нашем примере $f(x)=x^2+3x+5$, $p=11$, $k=1$. Есть только одно решение $x \equiv 4 \pmod{11}$ сравнения $x^2+3x+5 \equiv 0 \pmod{11}$. Пробуем его "поднять" до какого-нибудь решения по модулю $11^2$, но не получается, ибо $(11k+4)(11k+7)+5$ не делится 121. Значит, сравнение $x^2+3x+5 \equiv 0 \pmod{11^2}$ решений не имеет.

[nnosipov]

TOTAL в сообщении #663666 писал(а):

Но помощь от неё в данной задаче сомнительна.

Разумеется, в данном случае это просто стрельба по воробьям. Я вообще удивлён, как такая простая задача может обсуждаться на протяжении 3-х страниц. Разве что ради того, чтобы понять общий подход к таким задачам.

(Оффтоп)

Никак не могу вспомнить, в каком сборнике я встречал эту задачу. Она ведь хорошо известна.

-- Вт дек 25, 2012 23:19:25 --

(Оффтоп)

TOTAL в сообщении #663666 писал(а):

Вот (бестеоремный ) безтеоремный (как правильно? что-то запутался )

Во фразе "Попутал бестеоремный" второе слово пишется раздельно

[Батороев]

TOTAL в сообщении #663666 писал(а):

Вот (бестеоремный ) безтеоремный (как правильно? что-то запутался ) бестеоремный (это моё последнее слово ) подход (разные варианты которого здесь предлагались):

В нашем примере $f(x)=x^2+3x+5$, $p=11$, $k=1$. Есть только одно решение $x \equiv 4 \pmod{11}$ сравнения $x^2+3x+5 \equiv 0 \pmod{11}$. Пробуем его "поднять" до какого-нибудь решения по модулю $11^2$, но не получается, ибо $(11k+4)(11k+7)+5$ не делится 121. Значит, сравнение $x^2+3x+5 \equiv 0 \pmod{11^2}$ решений не имеет.

Бестеоремный подход в предлагаемых вариантах скорее склонился к тому, что выражение разложили на полный квадрат и остаточный член, кратный 11. Делимость остаточного члена на 11 наложило условие делимости на 11 и квадрата, что в свою очередь породило необходимость делимости обоих членов выражения на $11^2$. Взаимоисключающие условия такой делимости для обеих частей выражения и составили искомое противоречие.