Ok. I solved it but the second lemma is a bit ugly. maybe someone sees an improvement so we can improve that $ 484$ thing lemma1 there exists a quadratic non-residue $ a$ modulo $ p$ which is less or equal to $ \lfloor \sqrt {p} \rfloor + 1$ Proof: let $ a$ be the smallest quadratic non-residue mod $ p$. Now define $ b = \lfloor \frac {p}{a} \rfloor + 1$. Than $ ab < p + a$ meaning $ ab - p < a$ (obviouslly by substituting $ p = ka + r$ we easily conclude $ ab > p$). therefore $ ab - p$ must be a quadratic residue. we have (these are legendre symbols) \[ 1 = (\frac {ab - p}{p}) = (\frac {ab}{p}) = (\frac {a}{p})(\frac {b}{p}) \] and since $ a$ is a non-residue also $ b$ must be. but than because $ a$ is the smallest $ a\leq b = \lfloor \frac {p}{a} \rfloor + 1$ which leads to $ a\leq \lfloor \sqrt {p} \rfloor + 1$ lemma2 there exists a quadratic non-residue $ c$ mod $ p$ ($ p > 484$ ) such that \[ \frac {p}{3\lfloor \sqrt {p} \rfloor - 1} \leq c \leq \frac {3\lfloor \sqrt {p} \rfloor - 1}{2} \] Proof: consider $ a$ (the smallest non-residue mod$ p$). $ a\leq \frac {3\lfloor \sqrt {p} \rfloor - 1}{2}$ by first lemma (obviously $ \frac {3\lfloor \sqrt {p} \rfloor - 1}{2}\geq \lfloor \sqrt {p} \rfloor + 1$ for $ p > 8$) if $ a\geq \frac {p}{3\lfloor \sqrt {p} \rfloor - 1}$ than $ a = c$. But if that is not the case than we consider numbers $ a,4a,4^2a,4^3a...$. these numbers are all quadratic non residues mod $ p$ because legendre's symbol is multiplicative. and more. one of these numbers is between $ \frac {p}{3\lfloor \sqrt {p} \rfloor - 1}$ and $ \frac {3\lfloor \sqrt {p} \rfloor - 1}{2}$. that is because $ \frac {3\lfloor \sqrt {p} \rfloor - 1}{2} > 4\cdot \frac {p}{3\lfloor \sqrt {p} \rfloor - 1}$ for suficiently large $ p$ and it's therefore imposible for the sequence $ a,4a,4^2a,4^3a...$ to miss this interval. the inequality is equivalent to $ 8p < 9(\lfloor \sqrt {p} \rfloor)^2 - 6\lfloor \sqrt {p} \rfloor + 1$. now we substitute $ p = x^2 + d$(where $ d < 2x + 1$) and we get $ 0 < x^2 - 22x + 1$ which is true for all $ x$ grater than $ 21$ mening $ p > 22^2 = 484$ now for the problem assume the statement is false and $ p > 484$. therefore there exist $ 3\lfloor \sqrt {p} \rfloor$ consecutive numbers mod $ p$ that are all quadratic residues (one of them may be zero). now consider the set$ \{cM, c(M + 1), \cdots, c(M + 3\lfloor \sqrt {p} \rfloor - 1) \}$ where $ c$ is such a non-residue as in lemma2. because the legendre's symbol is multiplicative this now is a set of quadratic non-residues(one of them can be zero) that are at most $ 2c$ appart one from another.(if one is zero). we have $ 2c\leq3\lfloor \sqrt {p}\rfloor - 1$ by definition of $ c$. therefore it is imposible to pick $ 3\lfloor \sqrt {p}\rfloor$ consecutive numbers such that none of them would be a non-residue starting between $ cM$ and $ c(M + 3\lfloor \sqrt {p} \rfloor - 1)$. however this interval has lenght of $ c(3\lfloor \sqrt {p} \rfloor - 1)$ which is grater or equal than $ p$ due to definition of $ c$ and lemma2. we have therefore covered the whole modul with non-residues that are at most $ 3\lfloor \sqrt {p} \rfloor - 1$ appart. it is therefore impossible to choose $ 3\lfloor \sqrt {p} \rfloor$ consecutive numbers which do not contain a non-residue. Q.E.D all that remains is to check all prime numbers up to $ 484$. which is quite a suferable task. i didn't check them myself but i trust the problem holds and hope someone will now come up with a lower bound than $ 484$

I have proved that the set $ \{M, M+1, \cdots, M+ 2\lfloor \sqrt{p} \rfloor +2\}$ contains a quadratic non-residue to modulus $ p$ for all primes $ p$. Is it right?

Yes. if u consider $ 0\mod{p}$ as non-residue that is the best result u can get using the same method as i have done above. i however didn't consider zero as a non-residue. if u didn't consider $ 0$ as a non-residue than i don't know. u must have used modificated or completely different method. why don't u show us your proof

Here is my proof.

Attachments:
p.pdf (41kb)

I know I'm quite late to this question, but since apparently this a better result than the other ones in the thread, here's a proof showing that the set {$M, M+1, ..., M+2\lfloor \sqrt{p} \rfloor$} contains a quadratic non-residue mod p for all odd primes p and integers M, even while considering 0 as neither a quadratic residue or a quadratic non-residue. To show this, assume $M$ and $k$ are integers such that {$M, M+1, ..., M+k-1$} does not contain a quadratic non-residue. It would therefore be sufficient to show that $k < 2\lfloor \sqrt{p} \rfloor + 1$. To do this we take 2 cases: Case 1: The set {$M, M+1, ..., M+k-1$} does not contain a value 0 mod p. In this case, assume we take an integer $t$ such that $\frac{p-k}{k-1} \leq t \leq k$, and consider the arithmetic sequence $Mt, (M+1)t, ..., (M+k-1)t$. By considering the integers split into repeating regions of the residues in the set {$M, M+1, ..., M+k-1$} (length k) and the values not in the set (length p-k), we realize that the arithmetic sequence may not stay within one region of length $p-k$ (since $(M+k-1)t-Mt = t(k-1) \geq p-k$), and it may not "jump" over a region of length k (since the difference between consecutive terms is $t \leq k$), and so it's clear that there exists an element of the sequence that is equivalent to a value in {$M, M+1, ..., M+k-1$} mod p. Therefore there exists 2 elements $a, b$ in {$M, M+1, ..., M+k-1$} such that $at \equiv b \pmod p$, and since both $a$ and $b$ are non-zero quadratic residues mod p by definition, we must have $t$ a quadratic residue as well. This tells us that all integers within the set $[\frac{p-k}{k-1}, k]$ are quadratic residues mod p. Now for any positive integer $c \leq k$, consider $c, 4c, 9c, ...$. At least one of these terms must exist in the range $[\frac{k+1}{4}, k]$, because if not then there exists a positive integer $n$ such that $cn^2 \leq \frac{k}{4}$ and $c(n+1)^2 \geq k+1$, but then $4 < 4(\frac{k+1}{k}) \leq \frac{c(n+1)^2}{cn^2} = (1+\frac{1}{n})^2 \leq 4$, contradiction. But now if $\frac{p-k}{k-1} \leq \frac{k+1}{4}$, all values in the range $[\frac{k+1}{4}, k]$ are quadratic residues, and since for all $c \leq k$ there exists a positive integer $n$ such that $cn^2$ lies in this range, and is therefore a quadratic residue, c is a quadratic residue, which makes all values within $[1,k]$ quadratic residues. It's been proven in C3 that if this holds then $k < \sqrt{p}$, but $\frac{p-k}{k-1} \leq \frac{k+1}{4}$ implies $k \geq \sqrt{4p+5}-2 \geq \sqrt{p}$, contradiction, and so we must have $k < \sqrt{4p+5}-2 \leq 2\sqrt{p}-1 < 2\lfloor \sqrt{p} \rfloor + 1$, giving the desired result in this case. Case 2: The set {$M, M+1, ..., M+k-1$} does contain a value 0 mod p. In this case the set {$M, M+1, ..., M+k-1$} is equivalent to {$-a, -a+1, ..., -1, 0, 1, ..., b-1, b$} mod p for some non-negative integers $a$ and $b$, with $k = a+b+1$. If $p \equiv 3 \pmod{4}$, $-1$ is a quadratic non-residue, forcing $a = 0$, and since all values within $[1,b]$ being quadratic residues mod p implies $b \leq \lfloor \sqrt{p} \rfloor$, as mentioned earlier, $k = b+1 \leq \lfloor \sqrt{p} \rfloor +1 < 2\lfloor \sqrt{p} \rfloor + 1$, giving the desired result. If $p \equiv 1 \pmod{4}$, we may improve the lemma to state that if all integers in the range $[1,n]$ are quadratic residues mod p, then $n < \sqrt{p}-1$. To show this, let $t+1$ be the smallest quadratic non-residue mod p, and consider $t+1, 2(t+1), ..., t(t+1)$. These are all clearly quadratic non-residues. As all integers in the range $[p-t,p-1]$ are quadratic residues as -1 is a quadratic residue, and also no term is $p$ as $t+1 < p$ clearly, no term in the range $[p-t,p]$ appears in this arithmetic sequence of difference $t+1$. $t+1$ isn't big enough to jump this region, so clearly the sequence stays below it, forcing $t(t+1) < p-t$, which implies $t < \sqrt{p+1}-1$, and since clearly neither $p$ nor $p+1$ are perfect squares, $t < \sqrt{p}-1$, and since all integers in the range $[1,n]$ are quadratic residues mod p implies $n \leq t$, we must have $n < \sqrt{p}-1$. This therefore implies $n \leq \lfloor \sqrt{p} \rfloor - 1$. And now, since all values from in region $[1,a]$ are quadratic residues mod p (due to multiplying by -1) and all values in region $[1,b]$ are quadratic residues mod p, $a \leq \lfloor \sqrt{p} \rfloor - 1$ and $b \leq \lfloor \sqrt{p} \rfloor - 1$, and so $k = a+b+1 \leq 2\lfloor \sqrt{p} \rfloor - 1 < 2\lfloor \sqrt{p} \rfloor + 1$, giving the desired result. In every case, {$M, M+1, ..., M+k-1$} consisting of no quadratic non-residues implies $k < 2\lfloor \sqrt{p} \rfloor + 1$, and since {$M, M+1, ..., M+2\lfloor \sqrt{p} \rfloor$} is this set for $k = 2\lfloor \sqrt{p} \rfloor + 1$, it therefore must have a quadratic non-residue mod p, and we're done.