5
$\begingroup$

Let $p$ be an odd prime number.

  • If $p \equiv 3 \bmod 8$ or $p \equiv 5 \bmod 8$, $2$ is not a square mod $p$.
  • If $p \equiv 3 \bmod 8$ or $p \equiv 7 \bmod 8$, $-1$ is not a square mod $p$.

If $p \equiv 1 \bmod 8$, there seems to be no way to choose a single $n \in \mathbb{Z}$ such that $n$ is not a square mod $p$ regardless of the choice of $p$. Can one prove that this is not the case? What if we continue searching for residues mod 16?

In fact, the more general question I would like to know the answer to, is the following: Can there be a finite set of natural numbers $S$ such that that for each prime number $p$, there exists an $n \in S$ such that $n$ is not a square mod $p$?

$\endgroup$
1
  • $\begingroup$ I suspect not ... probably that follows from quadratic reciprocity. $\endgroup$
    – Angina Seng
    Apr 4, 2018 at 17:47

2 Answers 2

Reset to default
3
$\begingroup$

In other words given a finite set of numbers $S$ find a prime $p$ such that for all $n\in S$, $n$ is a quadratic residue modulo $p$. Now from quadratic reciprocity we have that

$$\left(\frac{n}{p}\right)=1 \Leftrightarrow p\equiv a_i \text{ (mod $4n$)}$$ where $a_i$ are some numbers depending on $n$.

It then follows from Dirichlet's theorem on primes in an arithmetic progression that there are infinitely many such primes.

$\endgroup$
5
  • $\begingroup$ This is not quite right, but the idea is fine and the details can be salvaged. If $n$ is odd then reciprocity only gives you a list of residues modulo $4n$, not $n$. So you do need to take more care in reconciling the congruences since they are not relatively prime moduli. You also do not have a priori any assumption that the values of $S$ are relatively prime, so it does depend somewhat on how $a_i$ are distributed. $\endgroup$
    – Erick Wong
    Apr 4, 2018 at 18:20
  • $\begingroup$ @ErickWong This is a spurious criticism, in fact there is no problem with the moduli. If you want both residues and non residues the you need some assumptions. Anyway this is a well known result in algebraic number theory. $\endgroup$
    – Rene Schipperus
    Apr 4, 2018 at 18:24
  • $\begingroup$ It is not a spurious criticism. You wrote down an if-and-only-if condition that is patently false (what is the list of $a_i$ for $n=2$ or $n=3$?). Of course I know it is a well-known result: my first sentence was that the idea can be salvaged, indicating that the final result is true. $\endgroup$
    – Erick Wong
    Apr 4, 2018 at 18:25
  • $\begingroup$ I have removed my downvote, but I still feel there is a gap between the existence of $a_i$ and the appeal to Dirichlet's theorem. It should be justified that we won't encounter a situation where, say, $p$ must be simultaneously one of $1,5 \pmod {8}$ and also $3,7,11 \pmod {12}$, which are inconsistent. tt's true that this won't actually happen as a consequence of the $a_i$ arising purely from quadratic residuosity constraints, but it isn't stated anywhere that there are any constraints on the $a_i$. $\endgroup$
    – Erick Wong
    Apr 5, 2018 at 1:57
  • 1
    $\begingroup$ @ErickWong Thank-you. My answer was not intented as a line by line complete proof. However the argument I have in mind is to add to the set $-1$ (and $2$ if you wish) and to replace all other numbers by their prime divisors. Then you have for a candidate $p$, $\left(\frac{q}{p}\right)=\left(\frac{p}{q}\right)$ and to make this latter $+1$ chose any residue classes and then use the Chinese remainder theorem. The modulus and class will be relatively prime, assuming you do not chose a class $\equiv 0(\mod q)$. But as you point out in your answer chosing $\equiv 1$ in all cases in much simpler. $\endgroup$
    – Rene Schipperus
    Apr 5, 2018 at 2:54
3
$\begingroup$

A simple consequence of quadratic reciprocity is that if $n$ is odd, then $$p \equiv 1 \pmod{4n} \implies \left(\frac{n}{p}\right)=1.$$

Pair this together with $p \equiv 1 \pmod 8 \implies \left(\frac{-1}{p}\right)=\left(\frac{2}{p}\right)=1$, and it's easy to see that for any finite set $S$, we can take $N$ to be the lcm of all elements of $S$, and then for any prime $p \equiv 1 \pmod{8N}$ the entirety of $S$ will be quadratic residues modulo $p$.

This also helps to explain why you are having particular difficulty finding a generic non-residue for primes congruent to $1$ mod $8$.

$\endgroup$
4
  • $\begingroup$ Downvote reason? $\endgroup$
    – Erick Wong
    Apr 4, 2018 at 18:34
  • $\begingroup$ Why do you have $4n$ ? Cause $n$ may be negative ? $\endgroup$
    – Rene Schipperus
    Apr 4, 2018 at 18:43
  • $\begingroup$ Oh, I think I get your point now. $\endgroup$
    – Rene Schipperus
    Apr 4, 2018 at 18:50
  • $\begingroup$ @ReneSchipperus It's because the characters of $p$ and $n$ mod $4$ are key to the statement of quadratic reciprocity. $\endgroup$
    – Erick Wong
    Apr 4, 2018 at 18:50

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .