Нужна помощь по формуле квадратичных вычетов...

[Regloger]

Уважаемые форумчане!
Срочно требуется ваша помощь… Завтра экзамен, но чтоб до него допустили нужно следующие: Вывести формулу квадратичных вычетов… В лекциях у нас написано вот что: «Если n является произведением двух простых чисел, p и q, то существует ровно (p-1)(q-1)/4 квадратичных вычетов по модулю n.» НО! Сам преподаватель сказал, что эта формула не верна! И нам нужно соответственно вывести правильную… при это правильная формула не сильно отличается от этой: «(p-1)(q-1)/4» ((это нам препод сказал, как бы помог… облегчил задачу… ))) что то типа знак другой и еще что то по мелочи… Короче, если кто знает, как выглядит интересующая нас формула дайте знать… Очень, очень надо) буду премного благодарен.

[RIP]

Видимо, считается, что $p\ne q$. Надо просто вспомнить китайскую теорему об остатках и количество квадратичных вычетов по простому модулю $p$ (не $\frac{p-1}2$, ведь 0 --- тоже квадратичный вычет...; а есть ещё чётное простое число $p=2$). Для простого модуля количество кв. вычетов выражается формулой $\left\lfloor\frac p2\right\rfloor+1$ ($\lfloor\cdot\rfloor$ --- целая часть).

[bot]

RIP писал(а):

... ведь 0 --- тоже квадратичный вычет...

Это вопрос соглашения - этот тривиальный случай чаще исключают, да и кв. вычетов-невычетов по простому нечётному модулю тогда одинаково становится: $\frac{p-1}{2}$.
Поэтому надо уточнять, что у преподавателя в рукаве - где рассматривается сравнение $x^2 \equiv a \pmod {pq} $ в кольце $\mathbb{Z}/pq\mathbb{Z}$ или в группе его обратимых элементов?
Судя по всему имеется в виду первый случай.