View topic - C 4 • Art of Problem Solving

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$ :blush:

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

C 4

Login