Модулярная арифметика-3

[nnosipov]

Пусть $p>2$, $q>1$ --- целые числа, причем $\gcd{(p-1,q)}=\gcd{(p,q)}=1$. Положим $r=(p-1)^{-1} \bmod{q}$ и $s=q^{-1} \bmod{(p-1)}$. Докажите, что $(1-rq^{-1}) \bmod{p}=(q^{-1}-s) \bmod{p}$.

P.S. Надеюсь, что данное утверждение не совсем очевидно и тянет на задачу в олимпиадном разделе. (К слову: начинается сезон районных/муниципальных школьных олимпиад.)

[Dendr]

Не то, что бы совсем-совсем очевидно, но все же доказательство очень и очень прямолинейное.
Не люблю модули, поэтому избавился от них сразу - и сразу все стало более чем наглядным.

(Оффтоп)

Пользуясь тем, что данные числа взаимно просты, мы можем домножать выражения под знаком модуля на $q$ или $p-1$, с взаимнооднозначным соответствием. Тогда равенства по модулю сводятся к условиям делимости:
$(1)(r(p-1)-1)\vdots q; r<q $
$(2)(sq-1) \vdots (p-1); s<p-1 $
Доказать:
$(3)(q-r+sq-1) \vdots p$
Очевидно, что если это выполняется, то так же выполняется и
$(3')(q+r(p-1)+sq-1) \vdots p $

Рассмотрим сумму
$r(p-1)+sq-1$

Из выражений (1), (2) следует, что она делится и на $q$, и на $p-1$. Но так как это взаимно простые числа, оно делится на их произведение: $r(p-1)+sq-1=Nq(p-1)$, где N - натуральное число.

Но при этом (см. неравенства в (1), (2)) $Nq(p-1)=r(p-1)+sq-1<q(p-1)+(p-1)q-1=2q(p-1)-1$
Следовательно, $N=1$
Таким образом, $q+r(p-1)+sq-1=q+q(p-1)=qp$. А это выражение, очевидно, делится на $p$.
Следовательно, (3') выполняется. Тогда выполняется и (3)
$\qed$

[nnosipov]

Dendr в сообщении #1428141 писал(а):

но все же доказательство очень и очень прямолинейное

Да, согласен.

Сама задача возникла в результате того, что другую задачу удалось решить двумя разными способами. Полученные ответы внешне не совпадали, и потребовалось некоторое усилие, чтобы установить их совпадение явным образом.

[maxal]

nnosipov в сообщении #1428069 писал(а):

Положим $r=(p-1)^{-1} \bmod{q}$ и $s=q^{-1} \bmod{(p-1)}$.

Когда два числа обращаются по модулю друг друга, это сразу наводит на мысль о Китайской теореме об остатках. В данном случае она даёт:

$$(p-1)r+qs\equiv 1\pmod{(p-1)q}.$$

Ну а из определения $r$ и $s$ становится понятно, что

$$(p-1)r+qs = 1 + (p-1)q,$$

откуда всё и следует.

[nnosipov]

maxal в сообщении #1428859 писал(а):

Когда два числа обращаются по модулю друг друга, это сразу наводит на мысль о Китайской теореме об остатках.

И с этой точки зрения задача становится очевидной.