НОМ Турция финален кръг 2002, зад.4

[drago]

Намерете всички прости числа [tex]p[/tex], за които броят на наредените двойки [tex](x,y), \, 0 \leq x,\, y < p[/tex] удовлетворяващи условието:

[tex]y^2 \, \equiv \, x^3 -x \, \pmod p[/tex]

е точно равен на [tex]p[/tex].

[mkmarinov]

Няма ли някакви ограничения за x и y?
[tex](x,y)[/tex] е решение импликира [tex](x+p,y+p)[/tex] е решение.

[drago]

O, разбира се, има се предвид по модул p. Коригирах го.

[ptj]

Понеже [tex]x^3-x\equiv 0\pmod 6[/tex] веднага се вижда, че при [tex]p=2[/tex] и [tex]p=3[/tex] решенията са точно по [tex]p[/tex] на брой, защото тогава [tex]y\equiv 0 \pmod p[/tex].

[drago]

Понеже [tex]x^3-x\equiv 0\pmod 6[/tex] веднага се вижда, че при [tex]p=2[/tex] и [tex]p=3[/tex] решенията са точно по [tex]p[/tex] на брой, защото тогава [tex]y\equiv 0 \pmod p[/tex].

Това да го считам само като наблюдение, нали?

[ptj]

Мисля хитрости за останалата част.

[grav]

При фиксирано [tex]x[/tex] броя на двойките е [tex]1+\left(\frac{x^3-x}p\right)[/tex]. Така общия брой двойки е
[tex]\sum 1+\left(\frac{x^3-x}p\right)=p+\sum \left(\frac{x^3-x}p\right)[/tex]

Също така

[tex]\left(\frac{(-x)^3-(-x)}p\right)=\left(\frac{-(x^3-x)}p\right)=\left(\frac{-1}p\right)\left(\frac{x^3-x}p\right)[/tex]

Когато
[tex]\left(\frac{-1}p\right)=-1[/tex]
дясната сума по-горе е равна на нула и значи [tex]p[/tex] решения.

[drago]

Това вече е почти решение. Почти защото ти доказваш, че при p=4k+3 условието е изпълнено.
Това, което остава, е да се види дали няма и други p-та !?

[grav]

Това вече е почти решение. Почти защото ти доказваш, че при p=4k+3 условието е изпълнено.
Това, което остава, е да се види дали няма и други p-та !?

Да, знам, и аз като pjt, само хвърлям идеи.

[drago]

Е, това е вярната идея, то почти не остана...

[grav]

Е, това е вярната идея, то почти не остана...

Това е ясно, но не ми е очевидно.

[drago]

Решението ти е много елегантно за първата част. Моето е по тромаво.
За останалото трябва да се забележи, че когато p=4k+1 броят на различните двойки (a, -a), като махнем (1,-1) и (0,0) е нечетен и за всяка такава двойка (x^3-x, (-x)^3 - (-x)) или и двете са квадратични остатъци или и двете не са.

Ето и моето решение: http://www.artofproblemsolving.com/Foru ... 5#p2556725

[grav]

Да, мерси, трябваше да се сетя. Ще го отдам на празнично настроение.