Разделы 
Дополнительно
Задача по математике - 944
2014-03-08 
Докажите малую теорему Ферма (в обобщенной формулировке), не опираясь на теорему Эйлера: если #p# - постое число, то для любого #a \in \mathbf{Z}# имеет место сравнение #a^{p} \equiv a (\mod p).#
Решение:
Ð ассмотрим вначале случай, когда чнсла #a# и #p# не являются взаимно простыми (то есть #a# делится на #p# Тогда #a \equiv 0 (\mod p),# а. следовательно, #a^{p} \equiv a (\mod p).# Пусть #\text{НОД}(a,p) = 1,# тогда числа #1 \cdot 2, 2 \cdot a, 3 \cdot a, \cdots, (p-1) \cdot a# имеют разные остатки при делении на #p.# Действительно, если допустить #i \cdot a \equiv j \cdot a (\mod p).# где #i,j = 1,2, \cdots, p-1,# то, в силу #\text{НОД}(a,p) = 1, i \equiv j (\mod p).# т.е. #i = j.# Отметим, что отличных от нуля остатков от деления на #p# ровно #p-1# штук, поэтому числа #1 \cdot 2, 2 \cdot a, 3 \cdot a, \cdots, (p-1) \cdot a# образуют полную чистему вычетов по модулю #p.# Перемножим отдельно числа #1,2,3, \cdots, (p-1)# и #1 \cdot 2, 2 \cdot a, 3 \cdot a, \cdots, (p-1) \cdot a# Тогда #(p-1)! \cdot a^{p-1} \equiv (p-1)! (\mod p) \iff (p-1)! \cdot a^{p-1} - (p-1)! \equiv 0 (\mod p) \iff (p-1)! \cdot (a^{p-1} - 1) \equiv 0 (\mod p).# Так как #(p-1)! \not \equiv 0 (\mod p),# следовательно, #a^{p-1} - 1 \equiv 0 (\mod p) \iff a^{p-1} \equiv 1 (\mod p).# Отсюда #a^{p} \equiv a (\mod p)# ■
Докажите малую теорему Ферма (в обобщенной формулировке), не опираясь на теорему Эйлера: если #p# - постое число, то для любого #a \in \mathbf{Z}# имеет место сравнение #a^{p} \equiv a (\mod p).#
Решение:
Ð ассмотрим вначале случай, когда чнсла #a# и #p# не являются взаимно простыми (то есть #a# делится на #p# Тогда #a \equiv 0 (\mod p),# а. следовательно, #a^{p} \equiv a (\mod p).# Пусть #\text{НОД}(a,p) = 1,# тогда числа #1 \cdot 2, 2 \cdot a, 3 \cdot a, \cdots, (p-1) \cdot a# имеют разные остатки при делении на #p.# Действительно, если допустить #i \cdot a \equiv j \cdot a (\mod p).# где #i,j = 1,2, \cdots, p-1,# то, в силу #\text{НОД}(a,p) = 1, i \equiv j (\mod p).# т.е. #i = j.# Отметим, что отличных от нуля остатков от деления на #p# ровно #p-1# штук, поэтому числа #1 \cdot 2, 2 \cdot a, 3 \cdot a, \cdots, (p-1) \cdot a# образуют полную чистему вычетов по модулю #p.# Перемножим отдельно числа #1,2,3, \cdots, (p-1)# и #1 \cdot 2, 2 \cdot a, 3 \cdot a, \cdots, (p-1) \cdot a# Тогда #(p-1)! \cdot a^{p-1} \equiv (p-1)! (\mod p) \iff (p-1)! \cdot a^{p-1} - (p-1)! \equiv 0 (\mod p) \iff (p-1)! \cdot (a^{p-1} - 1) \equiv 0 (\mod p).# Так как #(p-1)! \not \equiv 0 (\mod p),# следовательно, #a^{p-1} - 1 \equiv 0 (\mod p) \iff a^{p-1} \equiv 1 (\mod p).# Отсюда #a^{p} \equiv a (\mod p)# ■
