2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Пары обратных по модулю p
Сообщение25.04.2022, 19:18 


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

 Профиль  
                  
 
 Re: Пары обратных по модулю p
Сообщение25.04.2022, 23:25 
Аватара пользователя


07/01/16
1426
Аязьма
Соображения по возможному пути к решению. В начале ряда простых находятся подходящие $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$, которое не удастся "закрыть" подобными соображениями.

 Профиль  
                  
 
 Re: Пары обратных по модулю p
Сообщение26.04.2022, 12:34 


21/04/22
330
Пусть $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$ условие задачи не может быть выполнено.

 Профиль  
                  
 
 Re: Пары обратных по модулю p
Сообщение26.04.2022, 22:02 
Аватара пользователя


07/01/16
1426
Аязьма
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 выше

 Профиль  
                  
 
 Re: Пары обратных по модулю p
Сообщение26.04.2022, 23:55 


20/04/10
1776
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$ такога вида числа не принадлежат рассматриваемому интервалу.

 Профиль  
                  
 
 Re: Пары обратных по модулю p
Сообщение27.04.2022, 03:31 
Аватара пользователя


07/01/16
1426
Аязьма
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$

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 6 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group