Consecutive Quadratic Residues
For all prime numbers p , where p > 5 , define C p to be the set of all positive integers k such that k ≤ p − 2 with k and k + 1 as quadratic residues modulo p . For example, C 1 1 = { 3 , 4 } , because 3 , 4 , 5 are quadratic residues modulo 11 ( 5 2 ≡ 3 , 2 2 ≡ 4 , 4 2 ≡ 5 ( m o d 1 1 ) ) .
It can be proven that C p is non-empty for all p . Let m p be the smallest element of C p . Find the maximum value of m p among all p .
If this maximum doesn't exist, enter 0 as your answer.
The answer is 9.
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
1 solution
That's really interesting, how 2, 5, 10 come into play.
Thinking out loud, how can we characterize the solutions to
( a 2 + 1 ) ( b 2 + 1 ) = ( c 2 + 1 ) ?
For example, if a = 1 , we get the Pell's equation 2 b 2 + 1 = c 2 .
Log in to reply
Lots of infinite families. For instance ( a , 2 a 2 , 2 a 3 + a ) for any a . I got that one from the general Pell equation and the continued fraction convergents for a 2 + 1 .
Edit: And of course I skipped over ( a , a + 1 , a 2 + a + 1 ) . . .
Woah, nice solution
Of course 1 , 4 , 9 are always quadratic residues. So:
If 2 is a residue mod p , then m p = 1 .
If 5 is a residue mod p , then m p ≤ 4 .
If 1 0 is a residue mod p , then m p ≤ 9 .
But every prime p falls in at least one of the above categories: if 2 and 5 are not residues, then 1 0 is a residue, by properties of the Legendre symbol .
In all cases, then, m p is at most 9 . It suffices to find a prime p for which m p = 9 . It's necessary and sufficient that 2 , 3 , 5 , 7 are all non-residues mod p , although all we need is that it's sufficient (note that if 2 is a non-residue, so is 8 ). We can find a p that satisfies this by the Chinese Remainder Theorem together with some congruence conditions (hard!), or by manual/computer search (easier!). Roughly 1 / 1 6 of all primes will satisfy these conditions, so we shouldn't have to search for too long. I get p = 4 3 as the smallest such prime.
So the answer is 9 .