Олимпиада Туймаада по математике. Старшая лига. 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 нельзя удалять свои комментарии

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