Számelmélet: milyen p prímekre oldható meg a x^2 kongruens 2 (mod P) kongruencia?

utolsónak köszi! ezt már én is "megsejtettem2, de nem tudom normálisan bizonyítani.

X^2 kongruens 2 (mod p) akkor megoldható, ha:

2^((p-1)/2) kongruens 1 (mod p)

fogtam és beírogattam p helyére a prímeket 47ig és csak a 7 és a 17 lett jó. azokon látszik, hogy tényleg 4k+1 alakú, de biztos lehet ezt valahogy szépen is bizonyítani.

átszámoltam újra, tegnap este már kissé fáradt lehettem, de elvileg 7, 17, 23,31-re jó 37-ig nézve.

ezek 4k+1 vagy 4k-1es prímek, de nem az összes.

onnan jött ki az összefüggés, hogy ez akkor lesz ugye megoldható, hogy ha 2^((p-1)/2) kongruens 1el (mod p).

majd ezt átírtam legendre szimbólummal, arra ez lett, hogy (2/p). ez meg ránézésre is egy nevezetes tulajdonság, átírható úgy, hogy (-1)^((p^2-1)/8).

ebből jött ki, hogy a (p^2-1)/8nak kell párosnak lennie.

ez végigszámolva természetesen azt kapjuk, hogy p 8k+-1 alakú.

egyébként te is matek szakos vagy? mert van egy másik feladatom is, amin már jó ideje gondolkozom, de még nem sikerült megoldani:

egy bolha ugrál a számegyenesen. 0-ból indulva minden ugrással vagy egyet balra, vagy egyet jobbra ugorhat. hányféleképpen juthat el n ugrásból a k-adik számhoz?

erre van ötleted? bár mindjárt kiírom külön kérdésnek is.