Вопрос по теории чисел

[alisa-lebovski]

Сама я не по теории чисел, поэтому заранее извиняюсь за возможно глупый вопрос. Он возник в связи с одной задачей дискретной теории вероятностей.

Верно ли, что для любого простого числа $p$ можно подобрать такие целые числа $1\le m\le k\le l< p$, что $|kl-pm|=1$, причем их можно выбрать так, чтобы асимптотически получалось $m\sim p/4$; $k,l\sim p/2$, $p\to\infty$. Численно вроде получается, примерно так: $k\approx(p-\sqrt{p})/2$, $l\approx(p+\sqrt{p})/2$.

[angor6]

alisa-lebovski
По-моему, требования "для любого простого числа $p$" и "чтобы асимптотически получалось" противоречивы.

[iifat]

Я, в общем, тоже не по теории чисел, но коли уж числа от нуля до $p-1$ образуют группу, то у каждого в ней есть обратное в группе, а стало быть, для любого $k$ можно подобрать $l$ и $m$; неравенства будут выполняться автоматически (за исключением, возможно, $k$ и $l$), так что вполне вероятно...

[alisa-lebovski]

Да, тут я протупила: если $p$ - простое число больше 3, то и $p-1$, и $p+1$ будут составными (по крайней мере четными), их можно разложить на множители $k,l$ (при этом $m=1$). Так что первый вопрос снимается.

Остается второй. главный: можно ли выбрать $m\sim p/4$; $k,l\sim p/2$, $p\to\infty$?

[nnosipov]

alisa-lebovski в сообщении #1423603 писал(а):

$m\sim p/4$

Это бесплатно, если нужные $k$ и $l$ уже найдены. Но вопрос о существовании таких $k$ и $l$ не кажется очевидным.

[alisa-lebovski]

Просчитала на простых числах до 1000, вот конец:

$ \begin{tabular}{|c|c|c|c|r|c|c|c|} \hline $p$ & $k$ & $l$ & $m$ & $mp-kl$ & $k/p$ & $l/p$ & $m/p$ \\ \hline 937 & 434 & 516 & 239 & -1$ & .4632 & .5507 & .2551 \\ 941 & 453 & 484 & 233 & 1 & .4814 & .5143 & .2476 \\ 947 & 485 & 494 & 253 & 1 & .5121 & .5216 & .2672 \\ 953 & 491 & 493 & 254 & -1$ & .5152 & .5173 & .2665 \\ 967 & 442 & 466 & 213 & -1$ & .4571 & .4819 & .2203 \\ 971 & 466 & 498 & 239 & 1 & .4799 & .5129 & .2461 \\ 977 & 493 & 543 & 274 & -1$ & .5046 & .5558 & .2805 \\ 983 & 468 & 481 & 229 & -1$ & .4761 & .4893 & .2330 \\ 991 & 472 & 506 & 241 & -1$ & .4763 & .5106 & .2432 \\ 997 & 505 & 537 & 272 & -1$ & .5065 & .5386 & .2728 \\ \hline \end{tabular} $

[Lia]

Тема перемещена из форума «Помогите решить / разобраться (М)» в форум «Карантин»
по следующим причинам:

- неправильно набраны формулы (краткие инструкции: «Краткий FAQ по тегу [math]» и видеоролик Как записывать формулы);


Исправьте все Ваши ошибки и сообщите об этом в теме Сообщение в карантине исправлено.
Настоятельно рекомендуется ознакомиться с темами Что такое карантин и что нужно делать, чтобы там оказаться и Правила научного форума.

[Lia]

Тема перемещена из форума «Карантин» в форум «Помогите решить / разобраться (М)»

[Sonic86]

$kl=mp\pm1$ - арифметическая прогрессия с шагом $p$
Если $m\sim \frac{p}{4}$, то для выбора имеется $o(p)$ значений $m$.
В $r$ подряд идущих значений арифметической прогрессии хотя бы одно делится на некоторое простое $q:q=O(r)$.
Значит найдется хотя бы одно $m: mp+1=kl, k=o(p), l=\Omega(p)$.
Это не то, что требуется доказать, но это демонстрация того, что утверждение недалеко от истины. А дальше анализ становится труднее.
Если оно ложно, то опровергнуть его численным примером будет трудно.

[DeBill]

Как то очень хочется притянуть за уши примитивные корни из мультипликативной группы $\mathbb{Z}_p$ (Вики грит, что Виноградов доказал, что наименьший примитивный корень как раз типа $O(\sqrt{p})$(а если гипотеза Римана справедлива, то даже и $O(\log p)$)), но моего незнания теории чисел оказалось недостаточно для.

-- 03.11.2019, 02:41 --

Есть еще последовательность A046145 в OEIS : может, в ней есть что-то коррелирующее с таблицей ТС ?

[Andrey A]

alisa-lebovski в сообщении #1423493 писал(а):

... можно подобрать такие целые числа $1\le m\le k\le l< p$, что $|kl-pm|=1$, причем их можно выбрать так, чтобы асимптотически получалось $m\sim p/4$; $k,l\sim p/2$, $p\to\infty$

Перепишем требование $|kl-pm|=1$ так: $kl \sim pm$, тогда из требования $k,l\sim p/2$ следует $m \sim kl/p \sim (p/2)^2/p \sim p/4$. То есть требование $m\sim p/4$ лишнее. Вопрос сводится к поиску маленьких расстояний между обратными величинами по $\mod p$, что нормально, но еще и близких к точке $p/2$, что избыточно. Наименьшее расстояние между тремя точками — это, знаете ли, дело вкуса.
Условие $|kl-pm|=1$ можно переписать еще так: $kl=\pm 1 \mod p$. Положим $l=k+a$, где $a$ — некоторая маленькая величина, которую задаем в процессе перебора. Предыдущее сравнение тогда выглядит так: $k^2+ak=1 \mod p$ или $k^2+ak=-1 \mod p$. В таком виде это можно заводить в Вольфрам и выбирать $k$ наиболее близкие к точке $p/2$. Ваше решение для $p=953$ можно получить при $a=2$, а для $p$ вида $4n+1$ возможно и $a=0$ (с минус единицей, конечно). Не знаю что тут еще посоветовать.

[alisa-lebovski]

Мне надо не находить конкретные $k,l$ при заданном $p$ (с этим уже справилась), а доказать, что они существуют асимптотически. Что касается разности между ними, то она не является равномерно ограниченной, а мала только по сравнению с $p$.

[angor6]

alisa-lebovski в сообщении #1423691 писал(а):

доказать, что они существуют асимптотически.

То есть?

[alisa-lebovski]

Вопрос в том, можно ли выбрать $k,l\sim p/2$, $p\to\infty$?
Ну или что то же самое, $l-k=o(p)$, $p\to\infty$.

[angor6]

alisa-lebovski
Тогда, наверное, есть смысл уточнить, насколько могут отличаться $k$ и $l$?