Сложные задачи по теории чисел

[Maximum]

Ну, для кого как, конечно. Уж точно не простые. Как решать, представляю смутно.
Вот монстры:

1. Пусть $p>2$ - простое число, $q=\frac{p-1}{2}.$ Доказать, что $(q!)^{2}+(-1)^{q}\equiv 0\pmod p.$

2. Пусть $n>2.$ Доказать, что

$$ \prod_{\substack{1\leqslant x\leqslant n\\ (x,n)=1\\ (x+1,n)=1}}x\equiv 1\pmod n $$

3. Пусть $p$ - простое число вида $4k+1.$ Доказать равенство (тут и далее в задачах есть символ Лежандра)

$$ \sum_{m=1}^{p-1}m\left(\frac{m}{p}\right)=0 $$

4. Доказать, что если $p\equiv 1\pmod 4$ - простое число, то

$$ \sum_{x=1}^{p-1}x^{3}\left(\frac{x}{p}\right)=\frac{3}{2}p\sum_{x=1}^{p-1}x^{2}\left(\frac{x}{p}\right) $$

[Gordmit]

Первая задача по виду напоминает теорему Вильсона (о том, что

$$(p-1)!+1\equiv 0\pmod p$$

при простом $p$) и доказывается примерно так же. Для этого надо рассмотреть $1^2,2^2,\ldots,(\frac{p-1}{2})^2=q^2$ - все квадратичные вычеты по модулю $p$ и многочлен

$$f(x)=(x-1^2)(x-2^2)\ldots (x-q^2)-(x^q-1)$$

.

Степень этого многочлена не превосходит $q-1$, а решений у него будет не менее $q$, а именно все квадратичные вычеты по модулю $p$. (Для того, чтобы это показать, воспользуйтесь критерием Эйлера:

$$a^{\frac{p-1}{2}}\equiv \left(\frac{a}{p}\right)\pmod p$$

.)

Таким образом, все коэффициенты $f(x)$ делятся на p, а в частности, свободный член.

[bot]

Не только напоминает, но и прямо из неё следует. Надо просто вторую половину множителей в (p-1)! уменьшить на $p$.
Кстати теорему Вильсона можно доказывать, разбивая все множители кроме 1 и p-1 на пары взаимно обратных.

Эта же идея работает во второй. Если $x^2 \equiv 1 \pmod n$ и $(x+1)y \equiv 1 \pmod n$, то $x(x+1)y \equiv x \pmod n \Rightarrow x \equiv 1 \pmod n$.
При n чётном множителей нет => произведение считается равным 1 по определению.

Третья и четвёртая: $\sum\limits_{i=1}^{p-1} = \sum\limits_{i=p-1}^{1}$ и $\left(\frac{m}{p}\right)=\left(\frac{-m}{p}\right)$

Maximum писал(а):

Уж точно не простые.

Разве это сложно?

[Maximum]

Пасибки)) Решения до конца довести смог.

А как такое решать:
Доказать, что
$\lfloor\sqrt{n}+\sqrt{n+1}\rfloor=\lfloor\sqrt{4n+2}\rfloor$

Наверное, надо по определению. Но у меня не получается.
Я записываю: существую такие целые $k$ и $l,$ что
$k^{2}\leqslant 2n+1+2\sqrt{n^{2}+n}<k^{2}+2k+1$ и
$l^{2}\leqslant 4n+2<l^{2}+2l+1$
А как отсюда доказать, что $k=l$?

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

Еще задача: решить в натуральных числах:

$$1-\frac{1}{2+\frac{1}{3+\ldots+\frac{1}{n}}}= \frac{1}{x_{1}+\frac{1}{x_{2}+\ldots+\frac{1}{x_{n}}}}$$

Ребята, здесь цепная дробь! Но я не могу её набрать -- хотел поставить \ddots, но движок не понимает.

Здесь надо к общему знаменателю привести, а потом приравнять всё?

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

И вот:
пусть $a\in\mathbb{Z},a\neq b^{2},b\in\mathbb{Z}.$ Доказать, что существует простое $p,$ такое, что $\left(\frac{a}{p}\right)=1.$

[juna]

Maximum писал(а):

3. Пусть $p$ - простое число вида $4k+1.$ Доказать равенство (тут и далее в задачах есть символ Лежандра)

$$ \sum_{m=1}^{p-1}m\left(\frac{m}{p}\right)=0 $$

Для простого $p=4k+1$, если $m$ - квадратичный вычет, то и $p-m$ - квадратичный вычет. Аналогично, если $m$ - невычет, то и $p-m$ - невычет. Число вычетов и невычетов равны.

[Хорхе]

Maximum писал(а):

Пасибки)) Решения до конца довести смог.

А как такое решать:
Доказать, что
$\lfloor\sqrt{n}+\sqrt{n+1}\rfloor=\lfloor\sqrt{4n+2}\rfloor$

Это почти брутфорсом:
$\sqrt{n}+\sqrt{n+1}< \sqrt{4n+2}$ по Йенсену (но можно доказать и без него -- подумайте как), но $\sqrt{n}+\sqrt{n+1}>\sqrt{4n+1}$ для всех $n$ (если придумали, как доказать предыдущее без Йенсена, это докажете без труда). Ну теперь закончите рассуждение.

Добавлено спустя 14 минут 22 секунды:

Maximum писал(а):

Доказать, что существует простое $p,$ такое, что $\left(\frac{a}{p}\right)=1.$

Может, я совсем тупой, но мне кажется, что подойдет любой простой делитель числа $a-1$.
Видимо, имелось в виду $\left(\frac{a}{p}\right)=-1$? (Кстати, условие $a\neq b^2$ наводит на ту же мысль.)

[Maximum]

Неравенство Йенсена -- это какое, там, где определение вогнутой/выпуклой функции?

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

Цитата:

Но мне кажется, что подойдет любой простой делитель числа $a-1$

И точно!
В условии стоит именно 1, хотя опечатка очень вероятно (я просто уже две нашел).

Добавлено спустя 13 минут 33 секунды:

Доказательство того, что $\sqrt{n}+\sqrt{n+1}<\sqrt{4n+2}$

Действительно, извлечем из обеих частей очевидного неравенства $4n^{2}+4n<4n^{2}+4n+1$ квадратный корень (в силу монотонности корня знак сохранится), получим
$2\sqrt{n(n+1)}<2n+1$. К обеим частям неравенства прибавим $n+n+1$, получим:
$(\sqrt{n})^{2}+2\sqrt{n(n+1)}+(\sqrt{n+1})^{2}<(\sqrt{4n+2})^{2},$
откуда следует требуемое.

[neo66]

Maximum писал(а):

Еще задача: решить в натуральных числах:

$$1-\frac{1}{2+\frac{1}{3+\ldots+\frac{1}{n}}}= \frac{1}{x_{1}+\frac{1}{x_{2}+\ldots+\frac{1}{x_{n}}}}$$

Здесь надо к общему знаменателю привести, а потом приравнять всё?

Не советую. Попробуйте решить для малых $n =1,2,3$. Потом обратите внимание, на тождество:
$\frac{1}{2+x} + \frac{1}{1+\frac{1}{1+x}} = 1$

[Maximum]

Хорхе писал(а):

Ну теперь закончите рассуждение.

Видимо осталось сказать, что между $\sqrt{4n+1}$ и $\sqrt{4n+2}$ нет целых чисел. Я прав?

neo66 писал(а):

Попробуйте решить для малых $n$

Спасибо. Пробую.

Еще:

Обозначим через $S(n)$ сумму квадратов натуральных чисел $\leqslant n$ и взаимно простых с $n$. Тогда верно равенство:
$\sum\limits_{k=1}^{n}k^{2}=\sum\limits_{d|n}d^{2}S(n/d)=\sum\limits_{d|n}\frac{n^2}{d^2}S(d)$. Применяя это равенсто и формулу обращения Мебиуса доказать, что
$\frac{S(n)}{n^2}=\sum\limits_{d|n}\frac{1}{6}\cdot\mu(d)\cdot\left(\frac{2n}{d}+3+\frac{d}{n}\right)$

Добавлено спустя 1 час 25 минут:

Вот начал решать. Помогите завершить:

Пусть $\frac{a}{b}=\langle q_{0},q_{1},\ldots,q_{n}\rangle$ - несократимая рац. дробь, $q_{n}\geqslant 2,$ симметрическая (т.е $q_{0}=q_{n},q_{1}=q_{n-1},\ldots$). Доказать, что либо $a|b^{2}+1$ либо $a|b^{2}-1.$ Когда имеет место первый, а когда второй случай?

Я получил, что в случае симметрической дроби $P_{n-1}=Q_{n},$ причем ясно, что $P_{n}=a,Q_{n}=b$. Из этого как-то можно получить, наверное...

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

neo66 писал(а):

обратите внимание, на тождество

Классное тождество! Получилось, что $x_{1}=x_{2}=1,x_{3}=3,\ldots,x_{n}=n$

[Хорхе]

Maximum писал(а):

Видимо осталось сказать, что между $\sqrt{4n+1}$ и $\sqrt{4n+2}$ нет целых чисел. Я прав?

В точку! Так что там насчет задачи с квадратичным вычетом? Имелся в виду невычет?