1. Найти сумму квадратичных вычетов по модулю $%73$%.
  2. Найти произведение квадратичных невычетов по модулю $%103$%.

задан 17 Май '15 18:13

изменен 17 Май '15 21:15

%D0%92%D0%B8%D1%82%D0%B0%D0%BB%D0%B8%D0%BD%D0%B0's gravatar image


9917

10|600 символов нужно символов осталось
2

1) Требуется найти сумму $%1^2+2^2+\cdots+36^2$% по модулю $%73$%. Согласно известной формуле для суммы квадратов первых $%n$% натуральных чисел, легко доказываемой по индукции, $%1^2+2^2+\cdots+n^2=\frac{n(n+1)(2n+1)}6$%. В данном случае возникает множитель $%2n+1=73$%, который ни с чем не сокращается. При этом $%n$% делится на $%6$%. Поэтому по модулю $%73$% сумма будет равна нулю. Это же верно и в общем случае для простого числа $%p > 3$%.

2) Здесь можно применить теорему Вильсона. Произведение всех ненулевых остатков равно $%(p-1)!$%, что сравнимо с $%-1$% для любого простого $%p$%. Половина из этих остатков является квадратами по модулю $%p$%, а половина не является. Для квадратичных остатков получается произведение $%a=1^2\cdot2^2\cdot\ldots\cdot(\frac{p-1}2)^2$%. При этом $%-1$% сравнима по модулю $%p$% с произведением $%1\cdot2\cdot\ldots\cdot(\frac{p-1}2)\cdot(-\frac{p-1}2)\cdot\ldots\cdot(-2)\cdot(-1)=(-1)^{(p-1)/2}a$%. Ввиду нечётности числа $%(p-1)/2$% при $%p=103$%, получается, что $%a$% сравнимо с единицей по модулю $%p$%. Значит, произведение всех остальных остатков, не являющихся квадратами, сравнимо с $%-1$% по модулю $%p=103$%.

P.S. Термин "квадратичный невычет" является укоренившимся выражением, встречающимся в многочисленных учебниках. На мой взгляд, это филологическая нелепость, потому что "вычет" -- это старинный синоним остатка (вычитали, вычитали, и остался "вычет"). С этой точки зрения, выражение "неквадратичный вычет" является приемлемым, а "квадратичный неостаток" -- это нонсенс. Думаю, что причиной появления такого "словомонстра" является неудачная калька с иностранного. Лично я предпочитаю говорить о квадратах по модулю $%p$%.

ссылка

отвечен 17 Май '15 18:45

10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×339

задан
17 Май '15 18:13

показан
904 раза

обновлен
17 Май '15 18:45

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru