Сравнение по модулю - правильно ли решаю

[artempalkin]

Делаю первые шаги в работе со сравнением по модулю. Посмотрите, пожалуйста, правильно ли в целом решаю задачу.
Найти все простые $p$ такие, что

$$5^{p^2}+1 \equiv 0\pmod{p^2}$$

В общем, логика такая. Во-первых, предположим, что $5^{p^2}$ имеет общие делители с $p^2$. Это возможно лишь в случае, если $p=5$ (т.к. $p$ простое). Но

$$5^{25}+1 \not\equiv 0\pmod{25}$$

по очевидным причинам. Значит, $p \neq 5 \\$
Далее вспомним теорему Эйлера. В случае, если $p$ простое и $p\neq 5$,

$$5^{p^2-2}\equiv 1\pmod{p^2} \eqno{(1)}$$

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

$$5^{p^2}+1 \equiv 0\pmod{p^2}$$

$$25\cdot 5^{p^2-2}+1 \equiv 0\pmod{p^2}$$

$$25\cdot 5^{p^2-2} \equiv p^2-1\pmod{p^2}\eqno{(2)}$$

Далее складываем $(1)$ и $(2)$ и получаем

$$26\cdot 5^{p^2-2} \equiv 0\pmod{p^2}$$

Но

$$5^{p^2-2} \not\equiv 0\pmod{p^2},$$

поскольку $p \neq 5$. Отсюда и из отсутствия общих делителей у $5^{p^2-2}$ и $p^2$ следует, что

$$26 \equiv 0 \pmod{p^2}$$

Но, очевидно, $26$ не делится ни на один квадрат целого числа, а значит решений исходного уравнения нет. На этом доказательство заканчивается.

[Pphantom]

Тема перемещена из форума «Помогите решить / разобраться (М)» в форум «Карантин»
Не надо все сообщение запихивать в математический тэг. Так, конечно, красивее, но форумный движок подобного издевательства в больших объемах просто не выдержит. Так должны быть оформлены только формулы и обозначения.

Исправьте все Ваши ошибки и сообщите об этом в теме Сообщение в карантине исправлено.
Настоятельно рекомендуется ознакомиться с темами Что такое карантин и что нужно делать, чтобы там оказаться и Правила научного форума.

[Pphantom]

Тема перемещена из форума «Карантин» в форум «Помогите решить / разобраться (М)»

[nnosipov]

artempalkin в сообщении #1445411 писал(а):

Далее вспомним теорему Эйлера. В случае, если $p$ простое и $p\neq 5$,

$$5^{p^2-2}\equiv 1\pmod{p^2} \eqno{(1)}$$

А чему равна функция Эйлера от $p^2$?

[artempalkin]

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

artempalkin в сообщении #1445411 писал(а):

Далее вспомним теорему Эйлера. В случае, если $p$ простое и $p\neq 5$,

$$5^{p^2-2}\equiv 1\pmod{p^2} \eqno{(1)}$$

А чему равна функция Эйлера от $p^2$?

Вроде бы $\varphi (p^2)=p^2-2$, т.к. взаимно простыми с $p^2$ будут все числа до $p^2$, кроме $p$.

-- 18.03.2020, 18:30 --

Да, я понял, функция Эйлера не тому равна, потому что таких чисел больше будет... надо же, почему это мне в голову не пришло

-- 18.03.2020, 18:31 --

Тогда надо перерешивать...

[kotenok gav]

artempalkin в сообщении #1445431 писал(а):

кроме $p$.

И еще некоторых чисел.

-- 19 мар 2020, 02:27 --

artempalkin в сообщении #1445411 писал(а):

предположим, что $5^{p^2}$ имеет общие делители с $p^2$.

Ну как бы из сравнения очевидно, что это не так.

[artempalkin]

Тогда вот так:

Отбросив сразу случай, когда $p=5$, запишем ПРАВИЛЬНУЮ теорему Эйлера:

$$5^{p^2-p}\equiv 5^{p^2-2p+1+p-1}\equiv 5^{(p-1)^2+p-1}\equiv 1\pmod{p^2}$$

Подработаем данное нам уравнение:

$$5^{p^2}\equiv 5^{(p-1)^2+2p-1} \equiv p^2-1 \pmod{p^2}$$

Сложим их и получим

$$5^{(p-1)^2+p-1}\cdot \left[ 5^p+1 \right] \equiv 0 \pmod{p^2}$$

Сократим на первый множитель и получим упрощенную (хотя это как посмотреть) версию условия:

$$5^p+1\equiv \pmod{p^2} \rightarrow 5^p+1\equiv 5\cdot 5^{p-1}+1 \equiv 0\pmod{p} \eqno{(1)}$$

Или в окончательном виде

$$5\cdot 5^{p-1} \equiv p-1\pmod{p}$$

Запишем теперь теорему Эйлера для $p$

$$ 5^{p-1} \equiv 1\pmod{p}$$

Сложим два последних уравнения

$$ 6\cdot 5^{p-1} \equiv 0 \pmod p $$

Сократим на $5^{p-1}$:

$$6 \equiv 0 \pmod{p} $$

Получается, $p$ должен быть простым делителем 6-ки, то есть либо $2$, либо $3$.

Остается только проверить, какой из них подходит, т.к. в (1) я сделал необходимый переход (как это правильно назвать?).

-- 18.03.2020, 19:13 --

$3$ подходит, $2$ нет. Итого ответ: $p=3$.

И вот тут, конечно, вопрос, правильно ли я сделал. И даже если правильно, самый короткий был это путь или нет?

-- 18.03.2020, 19:16 --

kotenok gav в сообщении #1445437 писал(а):

И еще некоторых чисел.

Угу, до меня дошло не сразу.

kotenok gav в сообщении #1445437 писал(а):

Ну как бы из сравнения очевидно, что это не так.

Ну да, в каком-то смысле очевидно. Либо сразу видно, если проверить.

[nnosipov]

artempalkin в сообщении #1445439 писал(а):

И вот тут, конечно, вопрос, правильно ли я сделал. И даже если правильно, самый короткий был это путь или нет?

Правильно, но длинно. Сравнение $5^{p^2-p} \equiv 1 \pmod{p}$ равносильно сравнению $5^{p^2} \equiv 5^p \pmod{p}$, а это последнее --- сравнению $-1 \equiv 5 \pmod{p}$ (надеюсь, видите почему). Вот и все.

[artempalkin]

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

$5^{p^2} \equiv 5^p \pmod{p}$, а это последнее --- сравнению $-1 \equiv 5 \pmod{p}$ (надеюсь, видите почему)

Честно говоря, не очень. И я не очень тоже понимаю, как это вы находите ответ на вопрос задачи, даже не используя данное условие, а только теорему Эйлера. Получается, теорема Эйлера верна только для делителей 6? Или вы подразумеваете где-то использование условия задачи, когда пишете, что "это равносильно этому"?

[kotenok gav]

artempalkin в сообщении #1445453 писал(а):

даже не используя данное условие

Оно используется.

[nnosipov]

artempalkin
Первая равносильность не зависит ни от чего, а вот вторая, конечно, использует то, что дано (для левой части сравнения), а также теорему Ферма (для правой).

Кажется, я ненароком опустил нулевой шаг: из сравнения $5^{p^2-p} \equiv 1 \pmod{p^2}$ (предоставляемого теоремой Эйлера) следует сравнение $5^{p^2-p} \equiv 1 \pmod{p}$.

И еще одно кстати: без теоремы Эйлера здесь можно обойтись, достаточно малой теоремы Ферма.

[artempalkin]

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

вторая, конечно, использует то, что дано (для левой части сравнения), а также теорему Ферма (для правой)

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

Буду учиться. Спасибо большое!

-- 18.03.2020, 20:35 --

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

Кажется, я ненароком опустил нулевой шаг: из сравнения $5^{p^2-p} \equiv 1 \pmod{p^2}$ (предоставляемого теоремой Эйлера) следует сравнение $5^{p^2-p} \equiv 1 \pmod{p}$.

Да, вот это я как раз заметил и понял. Все-таки действий побольше, чем 2 :)

[nnosipov]

Если делать вот так:

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

И еще одно кстати: без теоремы Эйлера здесь можно обойтись, достаточно малой теоремы Ферма.

то будет еще короче.

[artempalkin]

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

И еще одно кстати: без теоремы Эйлера здесь можно обойтись, достаточно малой теоремы Ферма.

Я так понимаю, что чуток поплясать с бубном:

$$5^{p-1}\equiv 1\pmod p \rightarrow 5^p \equiv 5 \pmod p \rightarrow 5^{p^2} \equiv 5^p \pmod p$$

Второй знак следствия - возводим обе части в степень p.

Да, и никакой теоремы Эйлера.

[nnosipov]

artempalkin
Да, именно так.