Question

Prove that doesn't exist $N\in\mathbb{N}$ with property: for all primes $p>N$ exist $n\in{3, 4,\ldots, N}$ such that $n, n-1, n-2$ are quadratic residues modulo $p$.

Answer 1

By Dirichlet's theorem, there exists $p>N$ such that each prime $l\leq N$, with the exception of $l=3$, satisfies $(l/p) = (l/3)$. I claim that this $p$ is a counterexample. Indeed by multiplicativity $(m/p) = (m/3)$ for each $m \leq N$ that is not a multiple of 3. In particular $(m/p) = -1$ if $m \equiv -1 \bmod 3$. Each triple ${ n, n-1, n-2 }$ with $n \leq N$ contains one such $m$, and therefore cannot comprise three quadratic residues of $p$, QED.

What's the context? Seems rather tricky for homework; hope it's not a problem from an ongoing contest...

[Added later] In fact this seems to be the only construction, in the following sense:

Conjecture. For every prime $l \neq 3$ there exists $N$ with the following property: for all primes $p>N$ such that $(l/p) \neq (l/3)$ there is some $n \in \lbrace 3, 4, \ldots, N \rbrace$ such that each of $n$, $n-1$, and $n-2$ is a quadratic residue of $p$.

For example, if $l \in \lbrace 2, 5, 7, 11, 13, 17 \rbrace$ then we can take $N=121$. For $19 \leq l \leq 43$ we can use $N = 325$, and $N = 376$ works for $l=47$ and several larger $l$.

This can be checked as follows. For a positive integer $n$ let $s(n)$ be the unique squarefree number such that $n/s(n)$ is a square; e.g. for $n=24,25,26,27,28$ we have $s(n)=6,1,26,3,7$ respectively. Then $(n/p) = (s(n)/p)$ for all $p>n$. Given a small set $S$ of primes containing $l$ and a bound $N$, let $\cal N\phantom.$ be the set of all $n \in \lbrace 3, 4, \ldots, N \rbrace$ such that each of $s(n)$, $s(n-1)$, and $s(n-2)$ is a product of primes in $S$. Now try all $2^{|S|}$ ways to assign $\pm 1$ to each $(l'/p)$ with $l' \in S$, and see which ones make at least one of $s(n),s(n-1),s(n-2)$ a quadratic nonresidue for each $n \in \cal N$.

For $S = \lbrace 2, 3, 5, 7, 11, 13, 17 \rbrace$ and $N = 121$, we compute $${\cal N} = \lbrace 3, 4, 5, \ldots, 17, 18, 22, 26, 27, 28, 34, 35, 36, 50, 51, 52, 56, 65, 66, 100, 121 \rbrace,$$ and find that the only choices that work are the two that make $(l/p) = (l/3)$ for each $l \in S - \lbrace 3 \rbrace$.

Then if we put $l=19$ into $S$ and increase $N$ to $325$ we find that ${\cal N} \ni 325$, with $323 = 17 \cdot 19$, $324 = 18^2$, and $325 = 13 \cdot 5^2$. So the only way to avoid $(323/p) = (324/p) = (325/p) = 1$ is to make $(19/p) = +1$. We then incorporate $l=23$ by considering $n=92$, and $l=29$ using $n=290$, "etc." Computation suggests that there are lots of choices to make this work once we get past $l=19$, but I don't know how feasible it might be to prove this.

[The exhaustive computation over $2^{|S|}$ choices of $(l'/p)$ is what led me to the pattern $(l/p) = (l/3)$ in the first place. Once only two choices remained for $S = \lbrace 2, 3, 5, 7, 11, 13, 17 \rbrace$ I thought that a few more primes might whittle it down to zero and disprove the claim, but I kept seeing only two choices that differed only in the value of $(3/p)$, and the pattern in the other $(l/p)$ values soon became clear.]

Answer 2

This is Theorem 2 in D. Lehmer & E. Lehmer, On runs of residues, Proceedings of the American Mathematical Society, Vol. 13, No. 1 (Feb., 1962), 102-106. The proof there uses quadratic reciprocity and Dirichlet's Theorem on primes in arithmetic progression. They also deal with similar problems for k-th powers.