Остатки

[FirstAID]

А как можно выяснить , какие остатки может давать квадрат целого числа при делении на 379 ? Если на 7 , 6 и т.д , то тут мы непосредственно разбираем остатки . А если большое трёхзначное число и если повторения остатков вообще не видно ?
Или можно доказать , что квадрат любого целого числа при делении на 379 даёт каждый раз новый остаток . Т.е если число n ; то и n остатков ?

@темы: Олимпиадные задачи

Comments

[Trotil]

Ну, есть теория, правда, она проходится в вузе.

По факту - так как 379 - число простое, остатков будет ровно половина от диапазона [0..379].

Есть методика, позволяющая узнать, будет ли иметь решение уравнение x^2 = a mod 379 (a - остаток от деления на 379).

[FirstAID]

А если 375 ?

[Trotil]

C составными намного сложнее.

[Trotil]

Несколько примеров:

x^2 = a mod 3 -
имеет остаток 0 и половина из [1..2] = всего 2 возможных остатка {0,1}
x^2 = a mod 5 -
имеет остаток 0 и половина из [1..4] = всего 3 возможных остатка {0,1,4}

Теперь будем рассматривать степени.

x^2 = a mod 5^2 -
Всего чисел кратных 5 на множестве [0..25] пять штук. Все они будут давать остаток 0 при возведении в квадрат.
А половина из оставшихся будут вести себя обычным образом: (25-5)/2 =10 всего 10+1 возможных остатка

x^2 = a mod 5^3 -
имеет остаток 0 на числах, кратных 5? Нет, потому что 5^2 = 25 mod 125, а не 0.
Числа, кратные 5 могут давать остатки 0, 25, 50, 75, 100. Не факт, что будут. В действительности двух чисел из этого диапазона не будет (50,75), потому что остатки x^2 = a mod 5 - могут принимать значения 1,4, при умножении на 25 и получим 25, 100.
Сколько их? Чисел, кратных 25 пять штук. Они будут давать остаток ноль.
Чисел вида a*5 - 16 штук.
(a*5)^2 = a^2 * 25 mod 125
делим на 25 обе части
a^2 mod 5 - выяснили, что таких остатков 2 (см. выше)

Подытожим -
числа, кратные 5 будут давать 3 остатка.
Если их выбросить, останется чисел 125 - 125/5 = 100.
На них будут действовать традиционное правило - половина остатков.
Всего возможных остатков 50+3 = 53.

[Trotil]

Модули вида p*q.

Здесь всё просто (если разобраться с предыдущими случаями).
Для случая 7*5 имеем (4*3) = 12
Для случая 17*23 имеем 9*12 = 108 различных значения.
Оставлю на самостоятельный разбор.

Ну и наконец 375 = 3 *5^3
в ответе должно получиться 106=53*2

Можно попробовать найти
a(5^4=625) = 261
Можно доказать общую формулу:
a(p^e) = [p^e/6]+2 if p = 2; [p^(e+1)/(2p+2)]+1 if p > 2

[FirstAID]

О Господи , как всё сложно ..

[Trotil]

Да, это сложно. Но очень интересно!

[FirstAID]

А это с другими числами тоже прокатывает ?

[Trotil]

Конечно, это общий подход.

[FirstAID]

имеет остаток 0 и половина из [1..4]

А почему половина из диапазона ?

[FirstAID]

В действительности двух чисел из этого диапазона не будет (50,75), потому что остатки x^2 = a mod 5 - могут принимать значения 1,4, при умножении на 25 и получим 25, 100.

Не понятно , почему мы исключаем из остатков эти числа ?

[Trotil]

А почему половина из диапазона ?

Потому что уравнение x^2 = a mod p имеет ДВА решения. (x0,p-x0) - оба являются решениями.

Если у нас множество [1..4] - без нуля, т.к. оно кратно p (всегда!), то

будет пара элементов иметь остаток a1
Другая пара элементов будет иметь остаток a2.

А потом всё, элементы кончились. И половина возможных остатков будет незадейственна.

[Trotil]

> Не понятно , почему мы исключаем из остатков эти числа ?

Наоборот, оставляем.
Исключаем 50,75 - они не могут быть остатками.

Смотри.
Нужно выяснить какие остатки дают числа вида 5k.

(5k)^2 = 25 * k^2 mod 125
Можно сократить на 25
k^2 mod 5

остатки 1,4 - как уже выяснили.
Или, если не сокращать на 25, то это 25 и 100.

[FirstAID]

Т.е любое простое число в квадрате имеет (число остатков) = (само число) /2
Верно ?

[Trotil]

Оно имеет (p-1)/2 ненулевых остатков и собственно, ноль. Итого (p+1)/2.

[FirstAID]

Случай x^2 = a mod 5^3 не очень понятен :
Зачем мы на нём рассматриваем числа , которые делятся на 5 ?
И в чём идея рассмотрения ?

[Trotil]

> Зачем мы на нём расстраиваем числа , которые делятся на 5 ?

Затем, что числа, кратные 5 ведут себя иначе.

Свойство "половина остатков" верно только для чисел, не кратных p.

[FirstAID]

Чисел вида a*5 - 16 штук. (a*5)^2 = a^2 * 25 mod 125 делим на 25 обе части a^2 mod 5 - выяснили, что таких остатков 2 (см. выше)

А куда 16 делось ?

[Trotil]

> А куда 16 делось ?
10 остатков "25"
10 остатков "100"

Только там не 16, а 20. Ошибся в арифметике.

20 членов вида 5k (не кратных 25)

[FirstAID]

Вообще не догоняю = ( А может быть это где нибудь более подробно написано и более понятно для восприятия .
Без разницы какой учебник - вузовский , школьный - главное чтобы очень подробно было вот именно это расписано и рассмотрено на примерах . Случайно нет таких книг ?

[Trotil]

FirstAID, а зачем тебе?

Если просто для интереса - я так примерно показал на примерах, как оно работает. Суть хоть немного уловил?
Не думаю, что в школе это серьёзно пригодится.

Что касается книг - ну, там в других терминах это рассказывается. С использованием страшных слов "сравнение, квадратичный вычет, символы Якоби и Лежандра".

И вот на примерах, как я расписал, к сожалению, нигде особо не расписывается.

[FirstAID]

Trotil, в том то и дело , что не уловил =(
Ладно , завтра ещё попытаюсь понять ...

[Trotil]

FirstAID, по шагам, что нужно понять, структура:

1) x^2 = a mod 5
Здесь:
0 - особый случай.
[1..4] - даёт 4/2 = 2 остатка.
Полезно даже вручную перебрать, убедиться в тезисе.

2) x^2 = a mod 25
5k - особые случаи. таких чисел на множестве [0..24] - 5 штук.
(5k)^2 = 25k^2 - они всегда будут кратны 25, и всегда будут давать остаток 0. Можно проверить, например, найти остаток 20^2 от деления на 25.

Остальные 20 чисел дадут 10 остатков.
Итого 11 остатков.

3) x^2 = a mod 125
5k - особые случаи. таких чисел на множестве [0..124] - 25 штук.
Из них 0,25,50,75,100 - кратны 25 и дают в остатке 0:
(25k)^2 = 125 * 5k^2 = 0 * 5k^2 = 0
Остальные 20 чисел будут давать в остатке либо 25*1, либо 25*4=100.

Неособые случаи. Таких чисел 125-25 = 100.
Они ведут себя "нормально", то бишь 100 чисел дадут 50 различных остатков.

Короче, завтра перечитай.

[FirstAID]

Так ... Продолжим ...

[FirstAID]

Вроде понял .Для разбора , найдём количество остатков квадрата натурального числа при делении на 567
Пролог : `609=3*7*29`
1) `x^2=a `mod 3
всего два остатка : 0 или 1 = > 2 остатка
2)` x^2=a` mod 7 . Вроде тут нет особого случая , поэтому по стандарту : `(7+1)/2=4 ` остатка
3) `x^2=a ` mod 29 . Опять таки , нет особых случаев = > по стандарту : 15
=>
Эпилог : всего 15+4+2=21 остатков .
Верно ? ( наверное нет =))

[Trotil]

> Эпилог : всего 15+4+2=21 остатков .

Только перемножать надо: 15*4*2=120.
120 остатков - правильный ответ.

[Trotil]

Вот ответы для любого числа из интервала 1..10000:

oeis.org/A000224/b000224.txt

[FirstAID]

Trotil, Всё , понял . Потренируюсь ещё.
Большое спасибо за помощь и за большое количество времени , уделённого на объяснение !

[Trotil]

Случайны ли квадратичные вычеты?

Видео: www.mathnet.ru/php/presentation.phtml?option_la...
Текстовая версия: nd.ics.org.ru/doc/r/pdf/1714/1

(если кратко, то характеристики не похожи на случайные, в то же время описать их внятно математики пока не могут)

Последняя статья и последнее видео великого математика Владимира Игоревича Арнольда до его кончины.

[FirstAID]

ой , круто . Спасибо .На досуге посмотрю =)