Пары обратных по модулю p

[rightways]

Дано некоторое простое число $p$. Для каждого целого числа $a$, $1<a<p/2$ , найдется такое целое число $b$, что $p/2<b<p$ и $ab-1$ делится на $p$. Найдите все такие $p$.

[waxtep]

Соображения по возможному пути к решению. В начале ряда простых находятся подходящие $p\in\{5,7,13\}$, а дальше удача перестает улыбаться, по крайней мере, временно. Можно подметить, что для простых определенного вида никогда не будет решения для конкретных значений $a$ исходя из соображений делимости:

$$\begin{tabular}{|c|c|} \hline $p$&$a$\\ \hline $6m+5$&$3$\\ \hline $4m+3$&4\\ \hline $24m+13$&$8$\\ \hline $48m+25$&$16$\\ \hline \end{tabular}$$

(кроме ранее найденных представителей трех первых множеств, к которым рассуждение неприменимо, поскольку $a>p/2$). Остаются простые вида $48m+1$, и на них я задумался, не является ли этот путь тупиковым, и возможно таки найдется какое-либо простое вида $3\cdot2^n\!\cdot m+1$, которое не удастся "закрыть" подобными соображениями.

[mathematician123]

Пусть $p-1 = 2^s d$, где $d$ нечётное. Тогда $(2^s-1)p+1 = 2^{s+1}k$ для некоторого целого $k$. Пусть $2^s < \frac{p}{4}$. Тогда $2^{s+1}k \equiv 1 \pmod{p}$, причём $2^{s+1} < \frac{p}{2}$ и $k < \frac{p}{2}$. Пусть $2^s > \frac{p}{4}$. Тогда $d$ равно 1, 2 или 3. В первых двух случаях $p = 2^u+1$. При нечётном $u$ это невозможно, так как тогда $p$ делится на 3. При чётном $u$ получим, что $p+1$ делится на 3 и $3 \cdot \frac{p+1}{3} \equiv 1 \pmod{p}$. Рассмотрим случай $d = 3$. Тогда $p = 3 \cdot 2^u+1$. Если $u \equiv 1 \pmod{4}$, то $p \equiv 2 \pmod{5}$ и $5 \cdot \frac{2p+1}{5} \equiv 1 \pmod{p}$. Если $u \equiv 3 \pmod{4}$, то $p \equiv 0 \pmod{5}$. Если $u$ чётное, то $p \equiv 4 \pmod{9}$ и $9 \cdot \frac{2p+1}{9} \equiv 1 \pmod{p}$. Таким образом, при $p > 18$ условие задачи не может быть выполнено.

[waxtep]

waxtep в сообщении #1553451 писал(а):

я задумался, не является ли этот путь тупиковым, и возможно таки найдется какое-либо простое вида $3\cdot2^n\!\cdot m+1$, которое не удастся "закрыть" подобными соображениями

И похоже зря задумался: для любого $p=3\cdot2^n\!\cdot m+1$ возьмем $a=2^{n+1}$ и убедимся, что $m$ обязано быть четным. Действительно, пусть $b=3\cdot2^{n-1}\cdot m+j$ и тогда $ab-1\equiv j\cdot2^{n+1}-2^n-1\pmod{p}\Rightarrow2^{n+1}\cdot j=3\cdot k\cdot m\cdot 2^n+2^n+k+1$ и $k$ нечетно, а $m$ четно. Но тогда на самом деле наше $p=3\cdot2^{n+1}\!\cdot m^\prime+1$ и мы можем взять $a=2^{n+2}$, снова получая необходимость четности $m^\prime$, "и так далее без конца".

-- 26.04.2022, 22:20 --

Да, но случай $m=1\Rightarrow p=3\cdot2^n+1$ требует отдельного рассмотрения, т.к. там $a=2^{n+1}$ взять не получится. В этой части видимо рискую повторить часть решения, опубликованного участником mathematician123 выше

[lel0lel]

waxtep в сообщении #1553492 писал(а):

случай $m=1\Rightarrow p=3\cdot2^n+1$ требует отдельного рассмотрения, т.к. там $a=2^{n+1}$ взять не получится. В этой части видимо рискую повторить часть решения, опубликованного участником mathematician123 выше

По-моему, необязательно. Если $2^s<p<2^{s+1}$, то $p$ должно иметь вид $2^{s-1}3^{m}n+1$, где $m=\lfloor \log_3{2^{s-1}}\rfloor$. При $s>4$ такога вида числа не принадлежат рассматриваемому интервалу.

[waxtep]

lel0lel
У меня в конце концов получился такой наиболее внятный (из того, на что я видимо способен) вариант:

• проверяя $a\in\{3,4,5\}$ получаем подходящие $p\in\{5,7\}$ и множество кандидатов вида $p\in\{60m+1,60m+13\}$
• $60m+1$ всегда может быть представлено в виде $3\cdot2^n\cdot s+1$, где $s>1$ нечетно и "закрывается" при помощи $a=2^{n+1}$
• а вот $60m+13=12(5m+1)+1$ - не всегда, есть один специфический случай $5m+1=2^{4t}$; его "закроем" при помощи $a=9$, попутно приобретя $13$ в коллекцию подходящих $p$