 ТЕОРЕМА: Число p>1 - простое <=> p|(p-1)!+1
ДОКАЗАТЕЛЬСТВО:
=>. Пусть p>1 - простое, докажем, что p|(p-1)!+1.
При p=2 и p=3 доказательство очевидно. Можно доказывать p>=5. Так как Zp - поле, то для каждого X есть такое Y, что xy≡1 (mod p). Может окзаться, что для некоторых o<=x<=p-1 выполнено неравенство Y=X. Найдем все такие X, X^2≡1(mod p) => p|x^2-1 => p|(x+1)(x-1) => p|x+1 или p|x-1.
Если p|x-1, то x=1.
Если p|x+1, то x=p-1
Из этого следует, что множество (2,3...p-2) разбивается на такие пары, что произведение чисел каждой из них сравнимо с 1 по модулю p. Тоесть 2*3*...*(p-2)≡1 (mod p). => (p-1)!=1*(p-1)*2*3*...*(p-2)≡(p-2)≡-1 (mod p). Стало быть p|(p-1)!+1;
<=
Пусть p>1 и p|(p-1)!+1, тогда допустим, что p-составное число, значит существует такое q для которого 1<q<=p-1 и q|p. Ясно, что q|(p-1)! и q|(p-1)!+1, но тогда q|1, что невозможно. Полученное противоречие доказывает, что р - простое число. #.
| Разместил: KNOWED.RU Дата: 22.06.2009 Прочитано: 7372 | |  | |
|
28.12.2010 20:49
