Сколько таких чисел ?

[VladimirVK]

Здаствуйте уважаемые посетители форума. Сколько существует таких целых чисел , что при делении произвольного квадрата на эти числа,всегда будет в остатке квадрат? То-же самое для кубов и тд.?

[Батороев]

Я не понял вопрос...

[RIP]

И что тут дискуссионного?
Вопрос можно сформулировать так: Для каких натуральных $m$ все вычеты степени $d$ по модулю $m$ исчерпываются вычетами $0,1,2^d,\ldots,(\lceil m^{1/d}\rceil-1)^d$, т.е. их кол-во равно $\lceil m^{1/d}\rceil$?
Для $m=p^{\alpha}$, $p~-$ нечётное простое, количество вычетов степени $d$, которые взаимно просты с $p$, равно $\frac{p^{\alpha-1}(p-1)}{(d,p^{\alpha-1}(p-1))}$, что больше $\lceil p^{\alpha/d}\rceil$, если $p$ достаточно велико либо если велико $\alpha$ (при фиксированном $d$).
Для $m=2^{\alpha}$, $\alpha\geqslant3$, количество нечётных вычетов степени $d$ равно $\frac2{(d,2)}\cdot\frac{2^{\alpha-2}}{(d,2^{\alpha-2})}$, что больше $\lceil 2^{\alpha/d}\rceil$ при достаточно большом $\alpha$.
Учитывая еще вычеты степени $d$, которые не взаимно просты с $m$, оценки на $\alpha$ можно уменьшить.
Если $p^{\alpha}||m$ ($p~-$ произвольное простое), причём количество вычетов степени $d$ по модулю $p^{\alpha}$ больше $\lceil p^{\alpha/d}\rceil$, то и для $m$ количество их больше $\lceil m^{1/d}\rceil$ (это достаточное, но не необходимое условие). Это позволяет свести вопрос к конечному перебору для каждого фиксированного $d$.
Например, при $d=2\quad m$ может делиться лишь (пишу по памяти, поэтому неуверен) на $2$ в степени не выше четвёртой и $3,5,7$ в степенях не выше первой. Осталось отсеять лишнее, но это я уже не считал.

[VladimirVK]

Спасибо за Ваши ответы и извините за коряво сформулированный вопрос.Если можно я уточню так. Например любой квадрат при делении на числа 1,2,3,4,5,8,12,16 будет давать в остатке квадраты. Любой куб при делении на 1,2,9 , в остатке дает кубы. Четвертые степени , при делении на 1,2,3,4,5,8,16 - в остатке дают четвертые степени(только 0 или 1). А вопрос - найдутся-ли другие числа обладающие этими свойствами? Интуитивно кажется что нет , но доказать это не получается(ну тупой я ,тупой ,только не бейте ). Конечно , как и многие , пытаясь найти "самый" быстрый метод факторизации чисел , я и обнаружил этот , на мой взгляд интересный , факт. А с факторизацией это может быть связано следующим образом (опять же интуитивно кажется): при заданном числе А , подлежащим факторизации , найти соответствующие остатки от приделения на 3,4,5,8,12,16 ... и затем найти такой минимальный квадрат , который в сумме с получеными остатками даст при делении опять же на 3,4,5,8,12,16 ... остатки являющиеся квадратами. Например :
Пусть А=161:
тогда при делении на
3,4,5,8,12,16 остатками будут
2,1,1,1,5,1 соотвественно
тогда таким минимальным квадратом будет 64
т.е.
64+2,64+1, 64+1, 64+1, 64+5, 64+1 при делении на
3 ,4 ,5 ,8 , 12 , 16 соответственно ,дают в остатке квадраты. Таким образом 161+64 =225.
Возможно нужно использовать какую-нибудь суперпозицию от 1,2 3,4,5,8,12,16 ...
В этом и есть на мой взгляд предмет дискуссии , если конечно кому нибудь кроме меня это кажется интересным
Еще раз спасибо за проявленное внимание.

[RIP]

VladimirVK писал(а):

найдутся-ли другие числа обладающие этими свойствами?

Для квадратов любое такое число обязано иметь вид $m=2^{\alpha_0}3^{\alpha_1}5^{\alpha_2}$, где $0\leqslant\alpha_0\leqslant4$, $0\leqslant\alpha_1\leqslant1$, $0\leqslant\alpha_2\leqslant1$ (но не каждое такое годится). Скорее всего, Вы перечислили их все.

[VladimirVK]

Ну-да ,мне тоже так кажется. Контрпример 240 . Но статок от деления 324 на 240 есть 84 - не квадрат. Но вот доказательство ...

[RIP]

VladimirVK писал(а):

Но вот доказательство ...

приведено в моём самом первом сообщении. Чтобы его понять, надо знать некоторые сведения из элементарной теории чисел. Можете принять это утверждение на веру.

[VladimirVK]

Спасибо ,обязательно приму на веру и пойму Ваше доказательство. Просто меня смутило Ваше -"(но не каждое такое годится)"...

[RIP]

VladimirVK писал(а):

Просто меня смутило Ваше -"(но не каждое такое годится)"...

Легко доказывается, что $m$ обязано иметь такой вид, т.е. все другие заведомо не годятся. Но не все числа указанного вида годятся, для них надо просто отдельно проверить, удовлетворяют ли они условию (их немного, так что это нетрудно).

[VladimirVK]

Merci beaucoup! Теперь все ясно.
P.S.
Извините , я еще не разобрался с использованием тэгов , поэтому и формулировал словами.Обязательно исправлюсь

[maxal]

VladimirVK писал(а):

Конечно , как и многие , пытаясь найти "самый" быстрый метод факторизации чисел , я и обнаружил этот , на мой взгляд интересный , факт. А с факторизацией это может быть связано следующим образом (опять же интуитивно кажется): при заданном числе А , подлежащим факторизации , найти соответствующие остатки от приделения на 3,4,5,8,12,16 ... и затем найти такой минимальный квадрат , который в сумме с получеными остатками даст при делении опять же на 3,4,5,8,12,16 ... остатки являющиеся квадратами.

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

Теперь по существу метода как такового. Если представить $N$ в виде разности квадратов, скажем $N=x^2-y^2$, то $x$ и $y$ будут порядка величины $\sqrt{N}$. Например, в случае ala RSA для $N=pq$ с $1<p<q<N$ нетривиальное разложение единственно: $N=\left(\frac{p+q}{2}\right)^2 - \left(\frac{q-p}{2}\right)^2$.
Предположим теперь, что вы хотите найти $x$ и $y$ по модулям маленьких простых $p_1, \dots, p_k$, а затем получить и сами числа с помощью китайской теоремы об остатках. Чтобы гарантировать восстановление $x,y$ по их остаткам от деления на выбранные простые нужно, чтобы произведение этих простых было больше $\sqrt{N}$ (в примере с RSA это непосредственно вытекает из неравенства о средних: $x=\frac{p+q}{2}>\sqrt{pq}=\sqrt{N}$). Теперь прикинем объем вычислений.
По модулю каждого простого $p_i$ имеется около $p_i/2$ различных остатков являющихся квадратами, и поэтому сравнение $x^2-y^2\equiv N\pmod{p_i}$ будет в среднем иметь около $p_i/4$ решений $(x,y)$. Таким образом, суммарно придется перебрать и скомпоновать по китайской теореме об остатках около $\frac{p_1}{4}\frac{p_2}{4}\dots \frac{p_k}{4}=\frac{p_1 p_2\dots p_k}{4^k}$. Заметим, что вклад каждого простого в это произведение либо меньше (это хорошо!), либо больше (это плохо!) чем 1, в зависимости от того меньше $p_i$ чем 4 или нет. Но простых меньших 4 у нас всего-то раз, два и обчелся. Поэтому с ростом $k$ (и $p_i$) объем работ у нас неизменно растет, хотя с маленькими простыми скорость роста меньше. Так как произведение простых у нас в районе $\sqrt{N}$ (см. выше), то объем работ примерно выражается формулой $\frac{\sqrt{N}}{4^k}$, и мы заинтересованы в росте $k$, а следовательно в выборе как можно меньших простых. Поэтому можно предполагать, что $p_1, p_2, \dots, p_k$ - это первые $k$ простых чисел в их естественном порядке.
Например, для 512-битного $N$ потребуется около 50 первых простых, что дает выигрыш (не считая накладных расходов!) всего лишь в $4^{50}=2^{100}$ раз по сравнению с тупым поиском делителей в отрезке $[2,\sqrt{N}]$, что соответствует суммарному количеству итераций порядка $N^{1/2-1/5} = N^{0.3}$. Для 1024-битного числа количество итераций будет уже $N^{0.35}$ и т.д.
В общем, игра не стоит свеч.