Квадратичные вычеты и простые числа.

[Doil-byle]

Найти количество квадратичных вычетов и невычетов по модулю $p$, где $p$ - простое число. Для доказательства особых технических изысков не потребовалось, но результат сам по себе интересный.
Есть ещё более общая задача, за неё я пока не брался. Знаю, где посмотреть её решение, но надеюсь потом сам решить, когда вернусь к теории чисел.
Найти число квадратичных вычетов и невычетов по модулю $p_1 \cdot ... \cdot p_n$, где $p_1$, ... $p_n$ - различные простые числа.

[Sonic86]

Вообще, если что, это стандартная теорема из ТЧ.

[Doil-byle]

Я это утверждение встречал только в качестве задачи. И вообще, эдак любое содержательное утверждение можно называть "стандартной теоремой".

[bot]

Doil-byle, $x^2\equiv y^2\pmod{p}\Leftrightarrow x\equiv y\pmod{p} \vee x\equiv -y\pmod{p}$. Отсюда всё и следует.

Upd. Ничего олимпиадного.

[PAV]

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

[Doil-byle]

bot в сообщении #648827 писал(а):

Отсюда всё и следует.

Это тоже не само собой, а следует из леммы Евклида.

bot в сообщении #648827 писал(а):

Upd. Ничего олимпиадного.

Есть ещё вторая задача.

[Sonic86]

Doil-byle в сообщении #648843 писал(а):

Есть ещё вторая задача.

Число квадратичных вычетов равно $\frac{p_1-1}{2}...\frac{p_s-1}{2}$, что следует из $\mathbb{Z}_{p_1...p_k}^{\times}\cong\mathbb{Z}_{p_1}^{\times}\times...\times\mathbb{Z}_{p_k}^{\times}$ (или из китайской теоремы об остатках)