Задача с натуральными числами

VAL · Сообщение **VAL** » 31 янв 2012, 21:24

vicvolf писал(а):Source of the post
VAL писал(а):Source of the post
Идею изложил Hottabych.
Чуть подробнее так:
Если - нечетное простое число, то по модулю , очевидно, будет $\frac{p+1}2$ квадратов.

По теореме 202 (Бухштаб) в этом случае будет $\frac{p-1}2$ квадратов

Процитирую Вас же:

Вот и давайте считать!

Пусть

. Квадратами будут 0, 1 и 4, т.е. 3 числа. Что составляет ровно $\frac{5+1}2$ . Вы насчитали другое количество?

VAL писал(а):Source of the post
Если , то число является квадратом по модулю тогда и только тогда, когда оно будет квадратом по модулям и .

Это символ Якоби, а он будет равен 1, когда символы Лежадра равны не только 1, но и -1.
В данном случае имеем произведение не двух, а трех символов Лежадра:
$(\frac {a} {561})= (\frac {a} {3})(\frac {a} {11})(\frac {a} {17})$ , поэтому он равен 1, когда не только все 3 символа Лежадра равны 1, но и когда один из них равен 1, а остальные 2 равны -1.
Случаев когда (a/3) равен 1 по теореме 202 будет 1, и -1 столько же.
Случаев когда (a/11) равен 1 по теореме 202 будет 5, и -1 столько же.
Случаев когда (a/17) равен 1 по теореме 202 будет 8, и -1 столько же.
Вот и давайте считать!

Пожалуйста, посчитайте! Когда закончите, с удивлением обнаружите, что по модулю 561 имеется ровно $\frac{17+1}2\cdot\frac{11+1}2\cdot\frac{3+1}2=108$ квадратов. То есть, ровно столько, сколько я и написал давно тому назад.

PS: Как уже упоминалось, это вытекает из китайской теоремы об остатках. И никак не противоречит свойствам символа Лежандра.

Андрей А.

Можно так попробовать: от нуля до 280-ти имеется 160 взаимно простых и 121 не вз. пр. с модулем чисел. Среди последних точно нет оснований сравнимых квадратов. Выписываем их в строку (121) и следом любое вз. простое, к примеру 41. С 41-м квадратом сравнимы 58, 245, и 146-й, выписываем их в столбик под числом 41. Среди оставшихся чисел нет оснований квадратов, сравнимых с предыдущими, берем любое, записываем в строку и три сравнимых квадрата - в столбик, и т.д. В итоге на странице $121+4\cdot 40=281$ число, а в строке - $$121+40=161$$

число, но это и есть "худшая" серия. Каким бы не было 162-е число, модуль его абсолютно наименьшего вычета уже имеется на странице. Вроде бы $$162$$

и есть ответ.

VAL · Сообщение **VAL** » 01 фев 2012, 06:07

Андрей А. писал(а):Source of the post
Можно так попробовать:
[..]
Вроде бы и есть ответ.

Извините, Вы русский язык понимаете?!
Или надо на английском?

The set of squares modulo 561 contains exactly 108 numbers. Hence the answer is 108+1 = 109.

На русском этот ответ написан и обоснован в самом начале этой ветки.

Если Вы не согласны, приведите, пожалуйста 109 натуральных чисел, квадраты которых имеют попарно различные остатки от деления на 561.

PS: Excuse me for my poor English

Андрей А.

Да, Вы правы. Со вз. непростыми я погорячился.

vicvolf · Сообщение **vicvolf** » 01 фев 2012, 18:20

VAL писал(а):Source of the post
vicvolf писал(а):Source of the post
VAL писал(а):Source of the post
Идею изложил Hottabych.
Чуть подробнее так:
Если - нечетное простое число, то по модулю , очевидно, будет $\frac{p+1}2$ квадратов.

По теореме 202 (Бухштаб) в этом случае будет $\frac{p-1}2$ квадратов

Процитирую Вас же:
Вот и давайте считать!

Пусть . Квадратами будут 0, 1 и 4, т.е. 3 числа. Что составляет ровно $\frac{5+1}2$ . Вы насчитали другое количество?

Число 0 не является квадратичным вычетом, т.к по определению квадратичным вычетом по модулю р являются все числа а, для которых сравнение $x^2 \equiv a(mod p)$ имеет два решения (стр. 174 Бухштаб). Для числа 0 сравнение по модулю р имеет одно решение 0. Поэтому число квадратных вычетов по простому модулю определяется по формуле $\frac{p-1}2$ . Кроме того 0 не принадлежит к натуральным числам.

MrDindows · Сообщение **MrDindows** » 01 фев 2012, 18:36

vicvolf писал(а):Source of the post
Число 0 не является квадратичным вычетом, т.к по определению квадратичным вычетом по модулю р являются все числа а, для которых сравнение $x^2 \equiv a(mod p)$ имеет два решения (стр. 174 Бухштаб). Для числа 0 сравнение по модулю р имеет одно решение 0. Поэтому число квадратных вычетов по простому модулю определяется по формуле $\frac{p-1}2$ . Кроме того 0 не принадлежит к натуральным числам.

На странице 173 написано:
"В этой главе мы будем рассматривать только такие сравнения, записывая их в виде
x^2 = a (mod p)
причем будем считать а не принадлежащим нулевому классу, т. е. таким, что р не делит а."

Тоесть там заранее оговорено про 0, в общем же случае, определение такое = [url=http://ru.wikipedia.org/wiki/Квадратичный_вычет]http://ru.wikipedia.org/wiki/Квадра\xD1...ый_вычет[/url] , и 0 - является квадратичным вычетом.

VAL · Сообщение **VAL** » 01 фев 2012, 19:37

MrDindows писал(а):Source of the post
vicvolf писал(а):Source of the post
Число 0 не является квадратичным вычетом, т.к по определению квадратичным вычетом по модулю р являются все числа а, для которых сравнение $x^2 \equiv a(mod p)$ имеет два решения (стр. 174 Бухштаб). Для числа 0 сравнение по модулю р имеет одно решение 0. Поэтому число квадратных вычетов по простому модулю определяется по формуле $\frac{p-1}2$ . Кроме того 0 не принадлежит к натуральным числам.

На странице 173 написано:
"В этой главе мы будем рассматривать только такие сравнения, записывая их в виде
x^2 = a (mod p)
причем будем считать а не принадлежащим нулевому классу, т. е. таким, что р не делит а."

Тоесть там заранее оговорено про 0, в общем же случае, определение такое = [url=http://ru.wikipedia.org/wiki/Квадратичный_вычет]http://ru.wikipedia.org/wiki/Квадра\xD1...ый_вычет[/url] , и 0 - является квадратичным вычетом.

Считать ли 0 квадратичным вычетом , в конечном итоге, дело вкуса (и определения).
Но вот не считать его квадратом, игнорируя тождество $$0^2=0$$

(а в задаче нас интересовало именно это), может только Виктор В, в благородном порыве опровергнуть мое решение

vicvolf · Сообщение **vicvolf** » 01 фев 2012, 21:58

Hottabych писал(а):Source of the post
maxandreev писал(а):Source of the post
Добрый день. Подскажите, пожалуйста, идею решения такой задачи.
Не очень понятно, с чего начать...

Надо посчитать число квадратичных вычетов по модулю 561 и воспользоваться принципом Дирихле.

Здесь говорится о квадратных вычетах, а не о квадратах по модулю.

VAL писал(а):Source of the post
Идею изложил Hottabych.
Чуть подробнее так:
Если - нечетное простое число, то по модулю , очевидно, будет $\frac{p+1}2$ квадратов.
Если , то число является квадратом по модулю тогда и только тогда, когда оно будет квадратом по модулям и .

VAL писал(а):Source of the post
Считать ли 0 квадратичным вычетом , в конечном итоге, дело вкуса (и определения).
Но вот не считать его квадратом, игнорируя тождество

Не дадите определение квадрата по модулю с ссылкой, где оно встречается?

vicvolf · Сообщение **vicvolf** » 02 фев 2012, 07:41

VAL писал(а):Source of the post
в благородном порыве опровергнуть мое решение

Такой цели не ставлю :acute: - просто хочется найти правильное решение! Согласен, какое определена давать квадратичному вычету по модулю - дело вкуса. Давайте рассмотрим квадратичные вычеты с Вашим определением (с нулем). Для p=3 - 0,1; p=11 - 0,1,3,4,5,9; p=17 - 0,1,2,4,8,9,13,15,16. Правильно?

Hellko · Сообщение **Hellko** » 02 фев 2012, 10:31

это задача кстати из олимпиады для школьников. Вот я что то такое не умею решать, и таких слов незнаю. тем более в школе.

yourdomain.com