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?

  • 2
    $\begingroup$ What is the point of placing a bounty on a solved problem? Is anything unclear / to be explained in my solution? $\endgroup$ – W-t-P Apr 3 '19 at 13:27
  • $\begingroup$ 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 $\endgroup$ – 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<n'<2\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$.

  • $\begingroup$ 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?$ $\endgroup$ – function sug Apr 6 '19 at 14:57
  • $\begingroup$ @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$. $\endgroup$ – W-t-P Apr 6 '19 at 16:09
  • $\begingroup$ @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. $\endgroup$ – W-t-P Apr 6 '19 at 20:21
  • $\begingroup$ I can't understand why demand $n'<2\sqrt{p}$What's the point of this restriction? Thanks, $\endgroup$ – function sug Apr 7 '19 at 14:13
  • $\begingroup$ 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$. $\endgroup$ – W-t-P Apr 7 '19 at 16:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.