Нека p е естествено число по-голямо от 2.
p е просто тогава и само тогава, когато (p-1)! ≡ -1 (mod p)
Доказательство: Необходимост.
Ако p е просто, то
множеството Zp* = {1, 2, …, p-1} образува група спрямо умножението и всеки елемент a от
Zp*
притгежава реципрочен.
т. е. существува единствено решение на сравнението ax ≡ 1 (mod p). Да го означим с a-1.
Равенство a=a-1 на два реципрочни остатъка е възможно само
когато a = 1 или a = p-1.
Наистина, сравнението
a2 ≡ 1 (mod p) е рносилно на
(a-1) (a+1) ≡ 1 (mod p) ⇒ p/(a-1) или p/(a+1)
(символът p/A означава p дели a).
В първия случай a=kp+1 а в другия a=kp-1 .
Единствените такива елементи от Zp* са 1 и (p-1).
Останалите Zp* - числата от {2, 3, 4 , …., p-2} се групират по двойки реципрочни и
следователно тяхното произведение е сравнимо с 1.
Към него да добавим множителите 1 и (p-1).
Получаваме:
(p-1)! ≡ -1 (mod p)
Достаточност.
Нека p не е просто и притежава делител q>1. Да допуснем още, че (p-1)! +1 ≡ 0 (mod p).
Тогава (p-1)! +1 се дели на p и оттам на q.
Но q се намира като множетел в (p-1)! и следователно q не може да се дели на (p-1)! +1.
Следователно и за p това е невъзможно!
Полученото противоречие показва че p не е просто.
Примери за пръстени и идеали - Назад