Несколько вопросов по теории чисел

[MaхVT]

Доброго времени участникам форума!

Возникла необходимость в элементарном объеме изучить курс теории чисел. Делал я это без руководства преподавателя, спрашивать было не у кого. Более- менее с предметом я ознакомился, поэтому мои сообщения чаще всего (не всегда то есть) будут содержать решения задач с просьбой прокомментировать эти решения: правильны ли они и как можно короче (или красивее). Надеюсь на поддержку. (Я мог бы спрашивать на "родном" форуме, но там народу мало. )

Задача. Пусть $p=2^{2^n}+1$ - простое число Ферма. Доказать, что при $n\geqslant 1$ число $3$ - первообразный корень по модулю $p$.

Решение. Согласно критерию первообразного корня, 3 будет таковым, если $3^{2^{2^n}-1}\not\equiv 1\pmod{p}$. Докажем, что это сравнение действительно имеет место. Допустим, что наоборот $3^{2^{2^n}-1}\equiv 1\pmod{p}.$ Но тогда $3^{2^{2^n}}\equiv 3\pmod{p}.$ Так как $p$ - простое, то существует первообразный корень $g$ по этому модулю. Проиндексируем предыдущее сравнение по этому основанию. Получим: $2^{2^n}\cdot\text{ ind }3\equiv \text{ ind }3\pmod{p-1}.$ Отсюда получаем, что $2^{2^n}|\text{ ind }3.$ Таким образом, $\text{ ind}_{g}3=2^{2^n}t,t\in\mathbb{N}.$ Согласно определению индекса $g^{2^{2^n} t}\equiv 3\pmod{p}.$ Но $g^{2^{2^n}}\equiv 1\pmod{p},$ так как $g$ - первообразный корень.Значит, $3\equiv 1\pmod{p}.$ Противоречие.

На мой взгляд, несколько наворочено. Хочется попроще. (Кстати, а хотя бы правильно решено?)

[Gordmit]

MaхVT писал(а):

Согласно критерию первообразного корня, 3 будет таковым, если $3^{2^{2^n}-1}\not\equiv 1\pmod{p}$.

Вот это, по-моему, неправильно. Вместо этого сравнения должно быть

$$3^{2^{2^{n-1}}}\not\equiv 1\pmod{p}$$

.

[MaхVT]

Действительно, Вы правы. Это ж надо, как меня дикие степени подвели. Буду перерешивать.

[RIP]

А по-моему, должно быть

$$3^{2^{2^n-1}}\not\equiv1\pmod p$$

.

[MaхVT]

Подождите: должно быть $3^{2^{2^{n}-1}}$ Верно?

Добавлено спустя 1 минуту 15 секунд:

Пока писал, $RIP$ ответил.

[Gordmit]

Да-да, $3^{2^{2^n-1}}$, это была опечатка. Вот что значит отправить сообщение без предварительного просмотра

P.S. Повторная опечатка исправлена

[MaхVT]

По-моему, у Вас опять опечатка.

[RIP]

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

[MaхVT]

Пусть $g$ - первообразный корень по модулю $p.$ Тогда числа $g,g^{2},\ldots,g^{p-1}$ образуют приведенную систему вычетов по модулю $p$. Так как $p\neq 3,$ то найдется $k,1\leqslant k\leqslant p-1$ такое, что $3\equiv g^{k}\pmod{p}.$ Опять доказываем от противного. Возьмем $1\leqslant t<p-1$ и предположим, что $3^{t}\equiv 1\pmod {p}.$ Но тогда $g^{kt}\equiv 1\pmod {p}.$ Значит, $g^{kt}\equiv g^{p-1}\pmod {p}.$ Отсюда $kt\equiv p-1\pmod{p-1}.$ То есть $kt=(p-1)l,l\in\mathbb{N}.$ Теперь два случая. Если $k$ - нечетное, то ясно, что $p-1|t,$ получаем противоречие. Итак, в этом случае $3$ - первообразный корень. А вот четным число $k$ быть не может. Действительно, в противном случае 3 - квадратичный вычет по модулю $p$. То есть $\left(\frac{3}{p}\right)=1,$ и закон взаимности дает $\left(\frac{p}{3}\right)=1.$ По критерию Эйлера это значит, что $p\equiv 1\pmod{3}.$ То есть $3|p-1=2^{2^n}.$ Противоречие.

Теперь ошибок нет?

[RIP]

Всё верно. Только можно было то же самое сказать короче: в данном случае первообразный корень и квадратичный невычет суть одно и то же, поэтому надо проверить, что $\bigl(\frac3p\bigr)=-1$.

[MaхVT]

Спасибо за проверку.

Дайте совет, каким образом решать задачу:

Пусть $p>3$ - простое число. Докзать, что числитель суммы

$$ 1+\frac{1}{2}+\ldots+\frac{1}{p-1} $$

делится на $p^2.$

Добавлено спустя 1 час 12 минут 20 секунд:

Меня уже начинает нервировать то, что эта задача не получается у меня.

Добавлено спустя 1 час 11 минут 56 секунд:

Наверное, надо было в олимпиадные постить.

[RIP]

Для начала воспользуйтесь тем, что при $k=1,2,\ldots,p-1$ числитель дроби

$$\frac1{p-k}+\frac1k+\frac p{k^2}$$

делится на $p^2$.

[MaхVT]

С помощью указания RIP я смог привести данную в условии сумму к виду

$$ \frac{p^2}{1\cdot(p-1)p}+\frac{p^2}{2\cdot(p-2)p}+\ldots+\frac{p^2}{\frac{p-1}{2}\frac{p+1}{2}p} $$

Несомненно, числитель данной суммы делится на $p^2.$ Вроде бы должно быть очевидно, что и числитель исходной суммы делится на $p^2.$ Но меня терзают смутные сомнения.

[RIP]

Нет, так не годится. Так можно "доказать", что числитель любого рационального числа делится на $p^2$:

$$\frac ab=\frac{p^2a}{p^2b}$$

. В знаменателе не должно быть $p$.
С помощью моей предыдущей подсказки сведите задачу к следующей:
Доказать, что числитель суммы

$$\sum_{k=1}^{p-1}\frac1{k^2}$$

делится на $p$.
Для этого докажите, что числитель разности

$$\sum_{k=1}^{p-1}\frac1{k^2}-\sum_{k=1}^{p-1}{k^2}$$

делится на $p$ (в этих суммах не случайно одно и то же число слагаемых). Таким образом, всё свелось к такому:

$$\sum_{k=1}^{p-1}{k^2}\equiv0\pmod p$$

. Чтобы это доказать, домножьте сумму на $g^2$ ($g$ --- первообразный корень).

[MaхVT]

Да, RIP, ловко Вы разделались с задачей. Впрочем, у меня возникало желание в явном виде выписать $\sum\frac{1}{k^2},$ но я засомневался, что сумею это выписать в замкнутом виде. Вот и замечательно, что не стал выписывать. Попробую сделать так, как Вы сказали. Несмотря на то, что по теории чисел пять я уже получил, эту задачку я всё же дорешаю. Хорошенько всё обдумаю, распишу и выложу решение на проверку --- как я и для чисел Ферма сделал.