Делимость и алгебра.

[jrock]

Задание такое: $p,q \in \mathbb{P}, p \neq q$. Докажите что $p^{q-1} + q^{p-1} \equiv 1 (\mod pq) $.

Мои догадки: разложение группы в прямое произведение есть изоморфизм с прямым произведением. $C_{pq}\cong C_p \times C_q$. Потому что у нас два разных простых числа.
Видимо нужно как-то показать что единица (она видимо не будет нейтральным элементом в $C_{pq}$) сопоставляется с парой из произведения (у нас кстати прямая сумма).

[bnovikov]

jrock в сообщении #515339 писал(а):

Задание такое: $p,q \in \mathbb{P}, p \neq q$. Докажите что $p^{q-1} + q^{p-1} \equiv 1 (\mod pq) $.

Мои догадки: разложение группы в прямое произведение есть изоморфизм с прямым произведением. $C_{pq}\cong C_p \times C_q$. Потому что у нас два разных простых числа.
Видимо нужно как-то показать что единица (она видимо не будет нейтральным элементом в $C_{pq}$) сопоставляется с парой из произведения (у нас кстати прямая сумма).

Это - из пушки по воробьям. Попробуйте просто малую теорему Ферма.

[jrock]

Спасибо, догадался как дальше. Нужно преобразовать тождество, которое дано в теореме для p и q.
и все придет к $p^q + q^p \equiv q+p (\mod pq)$. Потом тоже самое получить для того, что нужно доказать.

[jrock]

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

[Sonic86]

Можно и обобщить:
$p_1,\ldots,p_r$ - различные простые, тогда $\left( \frac{p_1\ldots p_r}{p_1} \right)^{p_1-1}+\ldots +\left( \frac{p_1\ldots p_r}{p_r} \right)^{p_r-1} \equiv 1 \pmod {p_1\ldots p_r}$.

Кстати, тут снова вылазят удобные штуки $\frac{p_1\ldots p_r}{p_j}$, вот только их формализацию я не видел ни разу Ими, например, удобно записывать саму китайскую теорему об остатках: $x \equiv r_j \pmod{p_j} \Rightarrow x \equiv p_1 \ldots p_r \sum\limits_{j=1}^r \frac{r_j}{p_j} \left( \frac{p_1\ldots p_r}{p_j} \right)^{-1}_{\mod p_j} \pmod{p_1\ldots p_r}$. Если для простоты обозначить $s_j = \left( \frac{p_1\ldots p_r}{p_j} \right)^{-1}_{\mod p_j}$ - обратный элемент к $\frac{p_1\ldots p_r}{p_j}$ по модулю $p_j$, то будет покрасивше: $x \equiv r_j \pmod{p_j} \Rightarrow x \equiv p_1 \ldots p_r \sum\limits_{j=1}^r \frac{r_js_j}{p_j} \pmod{p_1\ldots p_r}$.

Вообще для $m=p_1\ldots p_r$ элемент $x \in \mathbb{Z}_m$ удобно записывать как $x \equiv m \sum\limits_{j=1}^r \frac{s_jr_j}{p_j} \pmod m$, где $r_j \in \mathbb{Z}_{p_j}$. Числа довольно легко складывать и перемножать - и то и другое покомпонентно.
Хотя это все оффтоп...

[bot]

(Оффтоп)

$\frac{p_1\ldots p_r}{p_j}$ удобно писать так: $p_1\ldots \widehat{p_j} \ldots p_r$

Здесь $ p_j$ говорит: счастливо всем оставаться, а я домой.

[jrock]

Sonic86
Спасибо за обобщение(честно говоря пока еще не понятное мне со третей строчки): что такое $r_j$ и громоздкая сумма справа от импликации еще и по модулю как-то.
У него явно есть много жизненных применений (вспоминаю RSA, хотя там было достаточно знания о разложении на сумму двух чисел), но у меня была задача все-таки разучить применение теоремы о разложении в прямое произведение.

bot
Про $\widehat{p_j}$ остроумно.

[Sonic86]

jrock в сообщении #515941 писал(а):

что такое $r_j$ и громоздкая сумма справа от импликации еще и по модулю как-то.

Ой! Вот это Вам пока точно не надо это оффтоп, мои бредни.

jrock в сообщении #515941 писал(а):

Про $\widehat{p_j}$ остроумно.

В Кострикине встречается, кстати. Т.е. вполне официальное обозначение.