Теория на числата - интерсна, квадратични остатъци.

[krassi_holmz]

Ето една интересна задача:
Нека [tex]p[/tex] е просто и [tex]a \leq p[/tex] е естествено. Да се докаже, че съществуват цели неотрицателни числа [tex]x,y[/tex], за които:
[tex]p|x^2 + y^2 + a, x^2+y^2+a < p^2[/tex]

[Реклама]

[Мирослав Стоенчев]

Д-во: Ако [tex]p=2,[/tex] то твърдението е вярно. Нека [tex]p[/tex] е нечетно просто число.Ще използваме следната:
Лема1. Ако [tex]p[/tex] е нечетно просто число, то има точно [tex]\frac{p-1}{2}[/tex] квадратични остатъци по модул [tex]p,[/tex] и следователно точно [tex]\frac{p-1}{2}[/tex] квадратични неостатъци по модул [tex]p.[/tex]

Сега да разгледаме числата [tex]a, a+1^{2},a+2^{2},...,a+(\frac{p-1}{2})^{2}.[/tex]
Ясно е че са [tex]\frac{p+1}{2}[/tex] на брой две по две несравними по модул [tex]p[/tex] числа, и съгласно лема 1 има поне едно число от разглежданите, което е квадратичен остатък по модул [tex]p.[/tex] Т.е. съществува [tex]y\in Z,[/tex] такова че
за някое [tex]i, 0\le i\le\frac{p-1}{2}[/tex] да имаме [tex]y^{2}\equiv -( a+i^{2})(mod (p))[/tex] . Можем да запишем минус, тъй като числата от разглежданата редица със знак минус са също [tex]\frac{p+1}{2}[/tex] на брой две по две несравними по модул [tex]p.[/tex]
Б.о.о. [tex]y\le p,[/tex] понеже разглеждаме сравнение по модул [tex]p.[/tex]
Накрая остана да съобразим, че ако [tex]\frac{p-1}{2}<y,[/tex] то [tex]y'=p-y\le \frac{p-1}{2}[/tex] също удовлетворява сравнението [tex]y'^{2}\equiv -( a+i^{2})(mod (p)).[/tex] Полагаме [tex]x=i,y=y',[/tex] като използваме, че [tex]0\le x,y\le \frac{p-1}{2},[/tex] получаваме [tex]x^{2}+y^{2}+a\equiv 0(mod(p))[/tex] и [tex]x^{2}+y^{2}+a\le 2(\frac{p-1}{2})^{2}+a\le 2(\frac{p-1}{2})^{2}+p<(p-1)p<p^{2},[/tex] с което твърдението е доказано.