Математикадан «Туймаада» олимпиадасы. Жоғары лига. 2016 жыл

Жай $p$ және $q$ сандарының қатынасы екіден артық емес. Біреуінің ең үлкен жай бөлгіші $p$, ал екіншісінің ең үлкен жай бөлгіші $q$ болатын, қатар келе жатқан екі натурал сан табылатынын дәлелдеңіз. ( А. Голованов )

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

Ануар вы правы, вот более правильное решение:

$БОО, ~ 2<p<q<2p$. (для $(p,~q)=(2,~3)$ очевидно)

Существует число $1\leq q^* \leq p-1$ такоe что $qq^* \equiv 1 \pmod p$.

Если $q^* < \dfrac{p}{2}$ подойдут $(qq^*-1,~qq^*)$:

$$\dfrac{qq^*-1}{p} < \dfrac{q}{2} < p \quad \dfrac{qq^*-1}{q} < q$$

Eсли $p-q^* < \dfrac{p}{2}$ подойдут $(q(p-q^*),~q(p-q^*)+1)$:

$$\dfrac{q(p-q^*)}{q} < q \quad \dfrac{q(p-q^*)+1}{p} < \dfrac{q}{2}+\dfrac{1}{p} < p$$

Неправильное решение:

$БОО, ~ p<q<2p$.

Достаточно брать числа $(pp^*-1,\ pp^*)$ где $p^* \in [1~,~\dots~,~q-1]$ такой что $\dfrac{pp^*-1}{q}$ натуральное число. Такой найдется так как $[p\cdot 1,\dots,p\cdot (q-1), p\cdot q]$ является полной системой остатков деления на $q$. Заметим что:

$$\dfrac{pp^*-1}{q} < p, \quad p^* \leq q-1 \leq 2(p-1)$$.

Очевидно что наибольшие простые делители для $pp^*-1$ это $q$, а для $pp^*$ это $p$.

А если $p<p*=r<q$ и $r$ простое

Дорогой и уважаемый пользователь agybaevanuar! Пожалуста можете немного быть вежливее и сообщяйте об ошибках немного мягче и не давите так сильно на человека! В противном случае я попрошу вас помолчать по возможности.

Удалите это сообщение. В противном случае я удалю ваш аккаунт

Так в matol нельзя удалять свои комментарии

Оказывается, админ жив)