2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




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

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

 
 
 
 
Сообщение13.12.2007, 06:46 
Аватара пользователя
RIP писал(а):
... ведь 0 --- тоже квадратичный вычет...

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

 
 
 [ Сообщений: 3 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group