2

Part of 2018 Serbia National Math Olympiad

Problems(1)

Number of odd quadratic residues mod n

Source: Serbia MO 2018 P2

n>1

be an integer. Call a number beautiful if its square leaves an odd remainder upon divison by

n

. Prove that the number of consecutive beautiful numbers is less or equal to

1+\lfloor \sqrt{3n} \rfloor

number theoryQuadratic ResiduesSequence