Three consecutive quadratic residues problem

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$.

• It is unfortunate that you phrase this as though it is a homework question. Also that you have not given enough detail on dependencies, with no idea why we should regard this as part of a research project. That is, why do you think this is true, what work have you put into this so far? – Will Jagy Jan 16 '12 at 20:43
• FWIW once $N\geq25$ the sequence $3,4,5,\ldots,N$ does contain for each $p$ some $n$ such that $n$ and $n-1$ are both squares mod $p$; indeed one of $4$, $9$, and $25$ works, because each is a square, as is one of $3$, $8$, and $24 = 3 \cdot 8$. It's not obvious to me whether one should expect such a construction to work also for $n,n-1,n-2$. – Noam D. Elkies Jan 17 '12 at 4:04
• Um, make that $N \geq 10$: either $5$, $9$, or $10$ works, because $5 \cdot 8 \cdot 10 = 20^2$ so one of $5$, $8$, $10$ is a quadratic residue and can be paired with $4$, $9$, or $9$ respectively. – Noam D. Elkies Jan 17 '12 at 6:06
• It might be worth mentioning that the theorem is indeed true for infinitely many primes, by a result of Chowla (and other improvements) that says that there are infinitely many primes with the property that the first non-quad. residue is about omega(log(p)). – Asaf Jan 17 '12 at 7:39
• The Lehmer's worked on problems like these; searching for "runs of residues" in Math Scinet should produce relevant literature. Also, the Vorlesungen über Zahlentheorie by Hasse contain a chapter where the connection between such problems and elliptic curves over finite fields is worked out in detail. – Franz Lemmermeyer Jan 17 '12 at 10:28

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.]

• Well, that was problem given to me by profesor at University - this problem isn't from any contest known to me. Yesterday I only prove that we can find $p$ prime that satisfies $(q_i/p) = a_i$ for finitely many primes $q_i$ and any $a_i\in\{-1, 1\}$. Later my friend finish this prove in the same way as you. Thank you very much for answer. – Seblis Jan 17 '12 at 11:55
• You're welcome. It seems that this might indeed be the only way to do it (see the material I added a few minutes ago). Can you reveal who was the "profesor at University" who asked the question, and in what context? – Noam D. Elkies Jan 17 '12 at 18:04
• I study at University of Warsaw and we have subject called Number Theory. There was set of optional tasks to do in december given to students by M. Skalba and M. Rotkiewicz on this subject. That was only not-so-obvious problem from this set and it looks very nice, so I simply wanted to know how to solve it :) – Seblis Jan 17 '12 at 18:40

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.