Find the smallest n such that for any prime p, at least 20 numbers 1,2, ..., n are quadratic residues not modulo p.
k is quadratic residue modulo p if there exists an integer j such that j^2 ≡ k (mod p).
To find the smallest value of n such that for any prime p, at least 20 numbers 1, 2, ..., n are quadratic residues modulo p, we can use the concept of Legendre symbols.
The Legendre symbol is defined as follows:
For a prime p and an integer a, the Legendre symbol (a/p) is defined as:
(a/p) = 1, if a is a quadratic residue modulo p
(a/p) = -1, if a is a non-quadratic residue modulo p
(a/p) = 0, if a is divisible by p
We can use this concept to solve the given problem.
1. Start by assuming the value of n as 20.
2. Iterate through all prime numbers p.
3. For each prime p, iterate through all numbers from 1 to n.
4. Calculate the Legendre symbol (a/p) for each number a.
5. Count the number of quadratic residues (Legendre symbol = 1).
6. If the count is less than 20 for any prime p, increment the value of n by 1 and repeat steps 2-6 until we find the desired number of quadratic residues for all primes.
7. Once we find the smallest value of n for which all primes have at least 20 quadratic residues, that will be our final answer.
Here's a Python code implementation for better understanding:
```python
import sympy
def find_smallest_n():
n = 20 # Start with assumption
primes = sympy.primerange(2, n+1)
while True:
found_all_residues = True
for p in primes:
quadratic_residues = 0
for a in range(1, n+1):
if sympy.legendre_symbol(a, p) == 1:
quadratic_residues += 1
if quadratic_residues < 20:
found_all_residues = False
break
if found_all_residues:
return n
n += 1
# Test the function
smallest_n = find_smallest_n()
print("The smallest value of n is:", smallest_n)
```
This code will iterate through prime numbers and check if at least 20 numbers are quadratic residues modulo p for each prime. If not, it increments n and repeats the process until we find the smallest value of n satisfying the condition.
Note: This algorithm might take some time to execute as it involves iterating through multiple prime numbers.