# show that the set $\{M, M+1, \cdots, M+ 2\lfloor \sqrt{p} \rfloor +2\}$ contains a quadratic non-residue to modulus $p$

Let $$M$$ be an integer, and let $$p$$ be a odd prime . Show that the set $$\{M+1,M+2,M+3,\cdots,M+ 2\lfloor \sqrt{p} \rfloor+2\}$$ contains a quadratic non-residue to modulus $$p$$ for all primes $$p$$

maybe can use this well know: Smallest quadratic nonresidue is less than square root plus one An odd prime $$p$$, $$a$$ is the smallest positive integer that is a quadratic nonresidue modulo $$p$$,then $$a<1+\sqrt{p}$$.

maybe can sove this problem?

• What is the point of placing a bounty on a solved problem? Is anything unclear / to be explained in my solution? – W-t-P Apr 3 '19 at 13:27
• sorry, I don't think you're going to be able to read this. Could you be more specific?and I bounty this problem hope can see clear solution or other methods to solve it,But Thank you – function sug Apr 6 '19 at 14:59

We know that there is a quadratic non-residue $$n$$ with $$2\le n<\sqrt p+1$$. Multiplying $$n$$ by the appropriate power of $$4$$, we can find a quadratic non-resdiue, say $$n'$$, in the range $$\frac12\sqrt p.
Consider the set $$S = \{Mn',(M+1)n',\dotsc,(M+2\lfloor\sqrt p\rfloor+2)n'\}\pmod p.$$ The "distance" in $$\mathbb Z_p$$ between any two consecutive elements of this set is $$n'<2\lfloor\sqrt p\rfloor+2$$, and there is no gap between the largest and the the smallest elements of the set since $$(M+2\lfloor\sqrt p\rfloor+2)n' > Mn' + p.$$ It follows that every interval in $$\mathbb Z_p$$ of length $$2\lfloor\sqrt p\rfloor+2$$ contains at least one element of $$S$$. In particular, there is an element of $$S$$ contained in $$\{M,M+1,\dotsc,M+2\lfloor\sqrt p\rfloor+2\}$$. In other words, there are $$x,y\in\{M,M+1,\ldots,M+2\lfloor\sqrt p\rfloor+2\}$$ such that $$y\equiv n'x\pmod p$$. Since $$n'$$ is a non-residue, so is (exactly) one of $$x$$ and $$y$$.
• Hello, Multiplying n by the appropriate power of 4,we can find a quadratic non-resdiue, say $n'?$, it means there exist $\delta$,such $4^{\delta} n=n'?$,such $\frac{1}{2}\sqrt{p}<4^{\delta} n<2\sqrt{p}$.if so,How to sure there exist this $\delta?$ – function sug Apr 6 '19 at 14:57
• @functionsug: Let $\delta$ be the largest integer with $4^\delta n<2\sqrt p$. Then $4^{\delta+1} n>2\sqrt p$; that is, $4\cdot 4^\delta n>2\sqrt p$, showing that $4^\delta n>\frac12\sqrt p$. Thus, $\frac12\sqrt p< 4^\delta n<2\sqrt p$, and we let $n'=4^\delta n$. – W-t-P Apr 6 '19 at 16:09
• @functionsug: informally, you just keep multiplying $n$ by $4$ till the resulting product hits the interval $(\frac12\sqrt p,2\sqrt p)$. You cannot jump over this interval since the right endpoint of the interval is 4 times larger than its left endpoint. – W-t-P Apr 6 '19 at 20:21
• I can't understand why demand $n'<2\sqrt{p}$What's the point of this restriction? Thanks, – function sug Apr 7 '19 at 14:13
• For the argument to go through, we want to ensure that there is a non-residue $n'$ in the interval $(\frac12\sqrt p,2\sqrt p)$. To this end, we multiply $n$ by $4$ till the resulting product is less than $2\sqrt p$. All these multiples of $n$ are quadratic non-residues, and the largest of them will land in the target interval $(\frac12\sqrt p,2\sqrt p)$. Try to work out a numerical example, such as $p=5003$, $n=3$. – W-t-P Apr 7 '19 at 16:24