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

Эта статья находится в разработке!

Теорема:

Пусть [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]