Processing math: 16%

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


Дано некоторое простое число p. Для каждого целого числа a, 1<a<p2, найдется такое целое число b, что p2<b<p и ab1 делится на p. Найдите все такие p. ( Абдыкулов А. )
посмотреть в олимпиаде

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

  0
2 года 11 месяца назад #

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

Я не знаю ато

  1
2 года 11 месяца назад #

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

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

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

  1
2 года 11 месяца назад #

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

  1
2 года 11 месяца назад #

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

  1
2 года 11 месяца назад #

+

пред. Правка 2   11
2 года 4 месяца назад #

пред. Правка 2   4
2 года 4 месяца назад #

пред. Правка 3   10
2 года 4 месяца назад #

  6
2 года 4 месяца назад #

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

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

  11
2 года 4 месяца назад #

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

  3
2 года 1 месяца назад #

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

  0
2 года 1 месяца назад #

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

  4
2 года 1 месяца назад #

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

Ответ: 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 — противоречие

  7
2 года 1 месяца назад #

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

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

  1
2 года 1 месяца назад #

это баян

  1
2 года 1 месяца назад #

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

  0
2 года 1 месяца назад #

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

пред. Правка 2   2
1 года 10 месяца назад #

Самое смешное, что эту задачу переоткрыли, и она оказалась на олимпиаде 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.

пред. Правка 2   9
8 месяца 11 дней назад #

Пусть 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