Find the smallest n such that for some prime p, at least 20 of the numbers 1,2,...,n are quadratic non-residues

modulo p.

I suppose this question isn't live anymore. Anyways next time please don't post brilliant problems (:

Well, here's a few hints for you to work out and be on the right track:
Step 1: quadratic reciprocity and CRT
Step 2: incorporate dirichlet's theorem into this.
Well, you can then see obviously that {3,5,6,7,10,11,12,13,14,17,19,20,22,23,24,26,27,28,29,31}. Now just try to prove that the desired answer is minimal. This is simple. Show that 2 and 3 MUST be quadratic residues.

Ok to clarify, the show that 2 and 3 must be quadratic residues part is to find the minimal.

To find the smallest n such that for some prime p, at least 20 of the numbers 1,2,...,n are quadratic non-residues modulo p, we can apply quadratic reciprocity and use trial and error.

Quadratic reciprocity is a theorem in number theory that establishes a relationship between quadratic residues and non-residues modulo p.

The theorem states that if p and q are distinct odd prime numbers, then the Legendre symbol (a/p) equals (-1)^(k * l), where k and l are the remainders of a/4 and p/4. Therefore, the Legendre symbol depends only on the residues of a and p modulo 4.

Using this theorem, we can devise a strategy to find the smallest n satisfying the given conditions:

1. Start with n = 20 and increment it until we find a prime p such that at least 20 of the numbers 1, 2, ..., n are quadratic non-residues modulo p.

2. For each value of n, check if there exists a prime p such that 20 numbers from 1 to n are quadratic non-residues modulo p.

3. To check if a particular p satisfies the condition, we need to calculate the Legendre symbol for each of the 20 numbers from 1 to n. Repeat this process for multiple p values until we find one that satisfies the condition.

4. If we find a prime p such that at least 20 numbers from 1 to n are quadratic non-residues modulo p, then we have found the smallest n that satisfies the given condition.

It may require some computational effort to find the smallest n, but by using quadratic reciprocity and trial and error, we can eventually determine the desired value.