20
правок
Изменения
Новая страница: «{{Теорема |id=th1 |statement= Пусть <tex>n</tex> нечетно, тогда для того чтобы <tex>n</tex> было простым необхо…»
{{Теорема
|id=th1
|statement=
Пусть <tex>n</tex> нечетно, тогда для того чтобы <tex>n</tex> было простым необходимо и достаточно, чтобы для каждого <tex>a\in\mathbb Z^*_n</tex> было выполнено <tex>a^\frac{n-1}{2}\equiv\left(\cfrac{a}{n}\right)\pmod n</tex>.
|proof=
Необходимость следует из критерия Эйлера для символа Лежандра. Докажем достаточность методом от противного.
Пусть для <tex>\forall a\in\mathbb Z^*_n : a^\frac{n-1}{2}\equiv\left(\cfrac{a}{n}\right)\pmod n</tex>, но <tex>n</tex> {{---}} составное.
<tex>a^{n-1}=(a^\frac{n-1}{2})^2\equiv\left(\cfrac{a}{n}\right)^2\pmod n</tex>
<tex>\left(\cfrac{a}{n}\right)^2=1\Rightarrow a^{n-1}\equiv 1\pmod n</tex>
Таким образом <tex>n</tex> {{---}} число Кармайкла.
Следовательно, <tex>n=p_1\times p_2\times\cdots\times p_s</tex>, где <tex>p_i</tex> {{---}} простое число, <tex>i=\overline{1,s}</tex>
Рассмотрим такое <tex>b</tex>, что <tex>\left(\cfrac{b}{p_1}\right)\equiv 1\pmod n</tex>
Найдем такое <tex>a</tex>, что:
<tex>\begin{cases}a\equiv b\pmod p_1\\a\equiv 1\pmod p_i,i=\overline{2,s}\end{cases}</tex>
Такое <tex>a</tex> существует по китайской теореме об остатках и принадлежит <tex>\mathbb Z^*_n</tex> (так как взаимно просто с <tex>n</tex>).
<tex>\left(\cfrac{a}{n}\right)=\left(\cfrac{a}{p_1}\right)\times\left(\cfrac{a}{p_2}\right)\times\cdots\times\left(\cfrac{a}{p_s}\right)=\left(\cfrac{a}{p_1}\right)=\left(\cfrac{b}{p_1}\right)=-1</tex>
<tex>a^\frac{n-1}{2}\equiv\left(\cfrac{a}{n}\right)\pmod n</tex>
<tex>\left(\cfrac{a}{n}\right)=-1\Rightarrow a^{n-1}\equiv -1\pmod n</tex>
<tex>a^\frac{n-1}{2}\equiv\left(\cfrac{a}{n}\right)=-1\pmod p_1</tex>
<tex>a^\frac{n-1}{2}\equiv\left(\cfrac{a}{n}\right)=-1\pmod p_2</tex> (противоречие с тем, что <tex>a\equiv 1\pmod p_i, i=\overline{2,s}</tex>)
Значит не верно наше предположение о том, что <tex>n</tex> {{---}} составное.
}}
|id=th1
|statement=
Пусть <tex>n</tex> нечетно, тогда для того чтобы <tex>n</tex> было простым необходимо и достаточно, чтобы для каждого <tex>a\in\mathbb Z^*_n</tex> было выполнено <tex>a^\frac{n-1}{2}\equiv\left(\cfrac{a}{n}\right)\pmod n</tex>.
|proof=
Необходимость следует из критерия Эйлера для символа Лежандра. Докажем достаточность методом от противного.
Пусть для <tex>\forall a\in\mathbb Z^*_n : a^\frac{n-1}{2}\equiv\left(\cfrac{a}{n}\right)\pmod n</tex>, но <tex>n</tex> {{---}} составное.
<tex>a^{n-1}=(a^\frac{n-1}{2})^2\equiv\left(\cfrac{a}{n}\right)^2\pmod n</tex>
<tex>\left(\cfrac{a}{n}\right)^2=1\Rightarrow a^{n-1}\equiv 1\pmod n</tex>
Таким образом <tex>n</tex> {{---}} число Кармайкла.
Следовательно, <tex>n=p_1\times p_2\times\cdots\times p_s</tex>, где <tex>p_i</tex> {{---}} простое число, <tex>i=\overline{1,s}</tex>
Рассмотрим такое <tex>b</tex>, что <tex>\left(\cfrac{b}{p_1}\right)\equiv 1\pmod n</tex>
Найдем такое <tex>a</tex>, что:
<tex>\begin{cases}a\equiv b\pmod p_1\\a\equiv 1\pmod p_i,i=\overline{2,s}\end{cases}</tex>
Такое <tex>a</tex> существует по китайской теореме об остатках и принадлежит <tex>\mathbb Z^*_n</tex> (так как взаимно просто с <tex>n</tex>).
<tex>\left(\cfrac{a}{n}\right)=\left(\cfrac{a}{p_1}\right)\times\left(\cfrac{a}{p_2}\right)\times\cdots\times\left(\cfrac{a}{p_s}\right)=\left(\cfrac{a}{p_1}\right)=\left(\cfrac{b}{p_1}\right)=-1</tex>
<tex>a^\frac{n-1}{2}\equiv\left(\cfrac{a}{n}\right)\pmod n</tex>
<tex>\left(\cfrac{a}{n}\right)=-1\Rightarrow a^{n-1}\equiv -1\pmod n</tex>
<tex>a^\frac{n-1}{2}\equiv\left(\cfrac{a}{n}\right)=-1\pmod p_1</tex>
<tex>a^\frac{n-1}{2}\equiv\left(\cfrac{a}{n}\right)=-1\pmod p_2</tex> (противоречие с тем, что <tex>a\equiv 1\pmod p_i, i=\overline{2,s}</tex>)
Значит не верно наше предположение о том, что <tex>n</tex> {{---}} составное.
}}
