|
Необходимость следует из критерия Эйлера для символа Лежандра. Докажем достаточность методом от противного.
Пусть для [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] — составное. | 