Бесконечно много 3

[rightways]

Дано натуральное число $a$ которое не является квадратом целого числа. Докажите, что существует бесконечно много простых $p$ для которых $a^{\frac{p-1}{2}}\equiv-1 ( mod p )$

[Sonic86]

Баян:
$a^{\frac{p-1}{2}}\equiv\left(\frac{a}{p}\right)\pmod p$
$a=e p_1^{a_1}...p_s^{a_s}, e=\pm 1$
$a\neq x^2\Rightarrow (\exists k)a_k\equiv 1\pmod 2$
$\left(\frac{a}{p}\right)=\left(\frac{e}{p}\right)\left(\frac{p_1}{p}\right)^{a_1}...\left(\frac{p_s}{p}\right)^{a_s}=(-1)^{\frac{p-1}{2}\sum\limits_j\frac{p_j-1}{2}}\left(\frac{e}{p}\right)\left(\frac{p}{p_1}\right)^{a_1}...\left(\frac{p}{p_s}\right)^{a_s}$.
Подберем $p$ так, чтобы $(\forall j\neq k)p\equiv 1\pmod{p_j}, p\equiv 1\pmod{4}, p\equiv -1\pmod{p_k}$. Такое $p$ существует, как лежащее в некоторой арифметической прогрессии вида $kt-1, t\in\mathbb{Z}, k=4p_1...p_s$, элементарное доказательство последнего факта см. в книге Хассе Основы теории чисел (если не вру, там это делается через круговые многочлены. Для $kt+1$ точно через круговые многочлены, а 2-й случай я не помню)