Материал из Викиконспекты
|
|
| Строка 10: |
Строка 10: |
| | |proof= | | |proof= |
| | * <tex> \Leftarrow </tex> Если '''p''' — не [[простые числа|простое]], тогда <tex> (p-1)! \vdots p </tex> (кроме <tex> p = 4 </tex>),но <tex> -1 </tex>, в любом случае, мы не получим. | | * <tex> \Leftarrow </tex> Если '''p''' — не [[простые числа|простое]], тогда <tex> (p-1)! \vdots p </tex> (кроме <tex> p = 4 </tex>),но <tex> -1 </tex>, в любом случае, мы не получим. |
| − | * <tex> \Rightarrow </tex> Пусть <tex>x : 1 \le x \le p-1</tex>, x {{---}} [[простые числа|простое]]. Для любого такого существует парный ему <tex> y</tex> такой, что <tex> xy \equiv 1(mod \text{ }p) </tex>. Может случиться, что для некоторых <math>x</math> будет выполнено равенство <tex>x=y</tex>. Тогда <tex> x^2 \equiv 1(mod \text{ }p) </tex>, значит <tex> (x-1)(x+1) \vdots p </tex>, значит <tex> x=1 </tex> или <tex>x=p-1</tex>. Таким образом последовательность <tex> 2,3, \ldots,p-2 </tex> разбивается на пары, что произведение чисел каждой из них сравнимо с 1 по модулю p. Таким образом <tex> (p-1)! \equiv 1(p-1)(mod \text{ }p)</tex>, откуда следует, что <tex> (p-1)! \equiv -1(mod \text{ }p)</tex> | + | * <tex> \Rightarrow </tex> Пусть <tex>x : 1 \le x \le p-1</tex>. Для любого такого существует парный ему <tex> y</tex> такой, что <tex> xy \equiv 1(mod \text{ }p) </tex>. Может случиться, что для некоторых <math>x</math> будет выполнено равенство <tex>x=y</tex>. Тогда <tex> x^2 \equiv 1(mod \text{ }p) </tex>, значит <tex> (x-1)(x+1) \vdots p </tex>, значит <tex> x=1 </tex> или <tex>x=p-1</tex>. Таким образом последовательность <tex> 2,3, \ldots,p-2 </tex> разбивается на пары, что произведение чисел каждой из них сравнимо с 1 по модулю p. Таким образом <tex> (p-1)! \equiv 1(p-1)(mod \text{ }p)</tex>, откуда следует, что <tex> (p-1)! \equiv -1(mod \text{ }p)</tex> |
| | }} | | }} |
Версия 20:31, 14 января 2011
Теорема Вильсона
| Теорема (Вильсон, О простых числах): |
p — простое [math] \Leftrightarrow (p-1)! \equiv -1(mod \text{ }p)[/math]. |
| Доказательство: |
| [math]\triangleright[/math] |
- [math] \Leftarrow [/math] Если p — не простое, тогда [math] (p-1)! \vdots p [/math] (кроме [math] p = 4 [/math]),но [math] -1 [/math], в любом случае, мы не получим.
- [math] \Rightarrow [/math] Пусть [math]x : 1 \le x \le p-1[/math]. Для любого такого существует парный ему [math] y[/math] такой, что [math] xy \equiv 1(mod \text{ }p) [/math]. Может случиться, что для некоторых [math]x[/math] будет выполнено равенство [math]x=y[/math]. Тогда [math] x^2 \equiv 1(mod \text{ }p) [/math], значит [math] (x-1)(x+1) \vdots p [/math], значит [math] x=1 [/math] или [math]x=p-1[/math]. Таким образом последовательность [math] 2,3, \ldots,p-2 [/math] разбивается на пары, что произведение чисел каждой из них сравнимо с 1 по модулю p. Таким образом [math] (p-1)! \equiv 1(p-1)(mod \text{ }p)[/math], откуда следует, что [math] (p-1)! \equiv -1(mod \text{ }p)[/math]
|
| [math]\triangleleft[/math] |
