Разделы 
Дополнительно
Задача по математике - 947
2014-03-08 
Пусть #p# и #q# - такие различные простые числа, что число #p-1# является делителем числа #q-1#. Докажите, что для любого целого числа #a,# взаимно простого с #pq,# имеет место сравнение #a^{q-1} \equiv 1 (\mod pq).#
Решение:
По условию #q - 1 = (p-1)k# для некоторого натурального чнсла #k.# Пусть целое число а взаимно просто с произведением #pq.# Тогда оно взаимно просто с каждым из чисел #p# и #q.# и потому, в силу малой теоремы Ферма, выполнены сравнения #a^{p-1} \equiv 1 (\mod p)# и #a^{q - 1} \equiv 1 (\mod q).# После возведения обеих частей первого из них в #k#-ю степень, получаем #a^{q-1} \equiv 1 (\mod p).# Таким образом, число #a^{q^{-1}} - 1# делится на два взаимно простых числа #p# и #q,# а потому делится и на произведение этих чисел. Это и означает, что #a^{q^{-1}} \equiv 1 (\mod pq).#
Пусть #p# и #q# - такие различные простые числа, что число #p-1# является делителем числа #q-1#. Докажите, что для любого целого числа #a,# взаимно простого с #pq,# имеет место сравнение #a^{q-1} \equiv 1 (\mod pq).#
Решение:
По условию #q - 1 = (p-1)k# для некоторого натурального чнсла #k.# Пусть целое число а взаимно просто с произведением #pq.# Тогда оно взаимно просто с каждым из чисел #p# и #q.# и потому, в силу малой теоремы Ферма, выполнены сравнения #a^{p-1} \equiv 1 (\mod p)# и #a^{q - 1} \equiv 1 (\mod q).# После возведения обеих частей первого из них в #k#-ю степень, получаем #a^{q-1} \equiv 1 (\mod p).# Таким образом, число #a^{q^{-1}} - 1# делится на два взаимно простых числа #p# и #q,# а потому делится и на произведение этих чисел. Это и означает, что #a^{q^{-1}} \equiv 1 (\mod pq).#
