OliForum Matematico

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:

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

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):

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)!

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