Lemmino sui RQ

[Rho33]

Ieri mattina riflettevo su una cosa abbastanza a caso: quanti sono gli interi $k \in [0,p-1]$ tali che sia $k,k+1$ sono entrambi residui quadratici? Ovvero, quante sono le coppie distinte non ordinate di residui quadratici consecutivi modulo $p$ ?

Bhe, dimostrare, o che ho cannato clamorosamente, oppure che quel conteggio restituisce:

Testo nascosto:

$\left \lceil \frac {p}{4} \right \rceil $

[matpro98]

Per $p=5$ si hanno i residui $0,1,4$. Conti come consecutivi anche $4,0$?

[Rho33]

Sì, anche quelli sono consecutivi! Avevo inserito la parte intera superiore per evitare confusione, la aggiusto distinguendo in casi (in questo modo però c'è un mini-mini-spoiler sulla soluzione):

Testo nascosto:

Se $p \equiv 1 \pmod 4$ allora il conteggio dà $\dfrac {p+3}{4}$ , mentre se $p \equiv 3 \pmod 4$ il conteggio dà $\dfrac {p+1}{4}$. Con $p=5$ quadra perché $5 \equiv 1 \pmod 4$ , quindi ci sono $2$ coppie, che sono quelle che hai trovato tu.

[Rho33]

Mini-rilancio: mi sono accorto che con il mio ragionamento è possibile trovare anche il numero di coppie di non residui quadratici consecutivi, ed il numero di coppie ordinate di (residuo,non residuo)!

[Troleito br00tal]

Aggiungo un mini-rilancio anch'io: usando il Lemma di Rho33, determinare quando 2 è residuo quadratico modulo p!