Тест Соловея-Штрассена

Материал из Викиконспекты
Перейти к: навигация, поиск
Эта статья находится в разработке!
Теорема:
Пусть [math]n[/math] нечетно, тогда для того чтобы [math]n[/math] было простым необходимо и достаточно, чтобы для каждого [math]a\in\mathbb Z^*_n[/math] было выполнено [math]a^\frac{n-1}{2}\equiv\left(\cfrac{a}{n}\right)\pmod n[/math].
Доказательство:
[math]\triangleright[/math]

Необходимость следует из критерия Эйлера для символа Лежандра. Докажем достаточность методом от противного.

Пусть для [math]\forall a\in\mathbb Z^*_n : a^\frac{n-1}{2}\equiv\left(\cfrac{a}{n}\right)\pmod n[/math], но [math]n[/math] — составное.

[math]a^{n-1}=(a^\frac{n-1}{2})^2\equiv\left(\cfrac{a}{n}\right)^2\pmod n[/math]

[math]\left(\cfrac{a}{n}\right)^2=1\Rightarrow a^{n-1}\equiv 1\pmod n[/math]

Таким образом [math]n[/math] — число Кармайкла.

Следовательно, [math]n=p_1\times p_2\times\cdots\times p_s[/math], где [math]p_i[/math] — простое число, [math]i=\overline{1,s}[/math]

Рассмотрим такое [math]b[/math], что [math]\left(\cfrac{b}{p_1}\right)\equiv 1\pmod n[/math]

Найдем такое [math]a[/math], что:

[math]\begin{cases}a\equiv b\pmod p_1\\a\equiv 1\pmod p_i,i=\overline{2,s}\end{cases}[/math]

Такое [math]a[/math] существует по китайской теореме об остатках и принадлежит [math]\mathbb Z^*_n[/math] (так как взаимно просто с [math]n[/math]).

[math]\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[/math]

[math]a^\frac{n-1}{2}\equiv\left(\cfrac{a}{n}\right)\pmod n[/math]

[math]\left(\cfrac{a}{n}\right)=-1\Rightarrow a^{n-1}\equiv -1\pmod n[/math]

[math]a^\frac{n-1}{2}\equiv\left(\cfrac{a}{n}\right)=-1\pmod p_1[/math]

[math]a^\frac{n-1}{2}\equiv\left(\cfrac{a}{n}\right)=-1\pmod p_2[/math] (противоречие с тем, что [math]a\equiv 1\pmod p_i, i=\overline{2,s}[/math])

Значит не верно наше предположение о том, что [math]n[/math] — составное.
[math]\triangleleft[/math]