Разделы 
Дополнительно
Задача по математике - 949
2014-03-08 
Пусть #p# и #q# - разлнчные простые числа. Докажите, что в этом случае имеет место сравнение #p^{q-1} + q^{p-1} \equiv 1 (\mod pq)#
Решение:
Действительно, согласно малой теореме Ферма, имеем: #p^{q-1} \equiv 1 (\mod q), q^{p-1} \equiv 1 (\mod p),# то есть имеет место делимость #(p^{q-1} - 1) \vdots q, (q^{p-1} - 1) \vdots p.# Поэтому #(p^{q-1} - 1)(q^{p-1} - 1) \vdots pq.# т.е. #p^{q-1}q^{p-1}-(p^{q-1}+q^{p-1})+1# делится на #pq,# а значит, ## делится на #pq.#
Пусть #p# и #q# - разлнчные простые числа. Докажите, что в этом случае имеет место сравнение #p^{q-1} + q^{p-1} \equiv 1 (\mod pq)#
Решение:
Действительно, согласно малой теореме Ферма, имеем: #p^{q-1} \equiv 1 (\mod q), q^{p-1} \equiv 1 (\mod p),# то есть имеет место делимость #(p^{q-1} - 1) \vdots q, (q^{p-1} - 1) \vdots p.# Поэтому #(p^{q-1} - 1)(q^{p-1} - 1) \vdots pq.# т.е. #p^{q-1}q^{p-1}-(p^{q-1}+q^{p-1})+1# делится на #pq,# а значит, ## делится на #pq.#
