Республиканская олимпиада по математике, 2022 год, 9 класс

Дано некоторое простое число $p$. Для каждого целого числа $a$, $1 < a < \frac{p}{2}$, найдется такое целое число $b$, что $\frac{p}{2} < b < p$ и $ab-1$ делится на $p$. Найдите все такие $p$. ( Абдыкулов А. )

Комментарий/решение

Здравствуйте как решать это напишите

Я не знаю ато

Скину свое решение задачи

Смотрите так как у нас p это простое мы можем сделать следущее рассмотрите это число как p-1 и оно будет давать один (вроде).

Дальше не знаю если честно поэтому кто можем напишите

типо как остаток

Я бы ответил, но не люблю спамеров

+

на самом деле ответы $p=5,7,13$ будет лучше если поменяешь решения,

можешь посмотреть решения здесь https://cdn.bc-pf.org/olympiads/math/national/final/2022/math9-1-sol.pdf

Извиняюсь за непрввишьное решение ,спасибо что показали

+11 рейтинга за не правилильное решение ☠️

Астана БИЛ ☠️☠️

Почти официальное решение.

Ответ: $p = 5, 7, 13$

Если $p < 20$, то методом подбора легко понять, что только $p=5, 7, 13$ удовлетворяют условию.

Теперь предположим $p > 20$.

Легко доказать, что для любого целого $a$, что $1 < a < p$ сущ. уникальное целое число $b$, что $1 < b < p$ и $ab \equiv 1 \pmod {p}$, поэтому из условия понятно, что не сущ. целых $a$ и $b$, что $1<a\leq b<\dfrac{p}{2}$ и $ab \equiv 1 \pmod {p}$ $(1)$

Если $p \equiv 2\pmod {3}$, то $\dfrac{p+1}{3},3<\dfrac{p}{2}$, что противоречит $(1)$. Значит $p \equiv 1\pmod {3}$. Аналогично доказываем, что $p \equiv 1\pmod {4}$. Один из $p+1,2p+1,3p+1,4p+1$ делится на 5, так как $\dfrac{p+1}{5},\dfrac{2p+1}{5}<\dfrac{p}{2}$, то это либо $3p+1$, либо $4p+1$. Если $5|3p+1$, то $\dfrac{3p+1}{10}, 10 <\dfrac{p}{2}$, что противоречит $(1)$. Значит $5|4p+1 \Leftrightarrow p \equiv 1\pmod {5}$. Выводим, что $р=60k+1$ для натурального $k$

$k=1 \Rightarrow p=61; 8*23 \equiv 1 \pmod {61}$, что противоречит $(1)$

$k=2 \Rightarrow p=121 \notin P \Rightarrow p \geq 181$

Докажем, что $p \equiv 1 \pmod {n}$, для всех целых $n$, что $1 < n < \sqrt{\dfrac{p}{2}}$.

База: $n=2,3,4,5$

Переход: $p \equiv 1 \pmod {i}$, для всех целых $i$, что $1 < i < n$, Докажем для $n$. Один из $p+1,2p+1,\ldots,p(n-1)+1$ делится на $n$. Допустим $p(i-1)+1$ делится на $n$ $(2 \leq i \leq n)$, из $(1)$ $\dfrac{p(i-1)+1}{n}>\dfrac{p}{2} \Rightarrow i>\dfrac{n}{2}$. Если $i<n$, то $i \nmid n$ $\Rightarrow НОК[n,i] \geq 2n$. Из предположения индукции:

$p(i-1)+1$ делится на $i$, поэтому делится и на $НОК[n,i]$. $НОК[n,i] \leq ni < \dfrac{p}{2}$, в силу $(1)$ $\dfrac{p(i-1)+1}{НОК[n,i]} > \dfrac{p}{2} \Rightarrow 2(i-1)*p + 2 > НОК[n,i]*p$ — противоречие, так как $НОК[n,i] \geq 2n > 2(i-1)$. Если $i=n$, то $p \equiv 1 \pmod {n}$ — переход доказан.

$p>128 \Leftrightarrow 8<\sqrt{\dfrac{p}{2} } \Rightarrow p \equiv 1 \pmod {8}$. Пусть $m=\left [\sqrt{\dfrac{p}{2} } \ \right ]$. Тогда среди $m,m-1,m-2,m-3$ найдутся два нечетных числа $m-a,m-a-2$, где $a=0,1$. Тогда очевидно, что они взаимнопросты. $p \equiv 1 \pmod {m-a,m-a-2,8}$ $\Rightarrow (m-a)(m-a-2)8|p-1$, так как они попарно взаимнопросты. Получаем: $p-1\geq (m-a)(m-a-2)8\geq (m-1)(m-3)8 > (\sqrt{\dfrac{p}{2} } -2)(\sqrt{\dfrac{p}{2} } - 4)8$. Раскрываем скобки:

$p-1>4p-48 \sqrt{\dfrac{p}{2} } + 64$ $\Rightarrow$ $48 \sqrt{\dfrac{p}{2}}>3p+65>3p$ $\Rightarrow$ $16 \sqrt{\dfrac{p}{2}}>p$ $\Rightarrow$ $\dfrac{256p}{2}>p^2$ $\Rightarrow$ $128>p$ — противоречие

Красивое решение

Сколько вы решали эту задачу?

это баян

но решение красивое

я официальное решение посмотрел и не понял и пользуясь их идеей 1-2 часа добивал

Самое смешное, что эту задачу переоткрыли, и она оказалась на олимпиаде Harvard-MIT 2023(можно найти на AOPS во вкладке contests, USA contests). Автор предложил наверняка лучшее из возможных решений:

Простые $p<20$ можно проверить вручную. Теперь для $p>20$, рассмотрим числа $\frac{p-5}{2}, 10$ они оба меньше $p/2$. Разность обратных им остатков $$\frac{2}{p-5}-\frac1{10}=\frac{p-1}2$$ Поэтому они не могут быть оба больше $p/2$.

Пусть $p$ $>$ $20$:

Если $p \equiv 1 \pmod{5}$

Тогда $\dfrac{p-5}{2}×\dfrac{2p-2}{5} \equiv 1 \pmod{p}$

Если $p \equiv 2 \pmod{5}$

$\dfrac{p-2}{5}×\dfrac{p-5}{2} \equiv 1 \pmod{p}$

Если $p \equiv 3 \pmod{5}$

$\dfrac{3p+1}{10}×10 \equiv 1 \pmod{p}$

Если $p \equiv 4 \pmod{5}$

$\dfrac{p+1}{5}×5 \equiv 1 \pmod{p}$

Противоречие. Случай $p < 20$ легко разбирается, и мы получаем ответы $p=5,7,13$