1
$\begingroup$

I've been struggling to find the solution for this question for a while now and thought I might as well ask for some help. The question is:

Let $r$ be the smallest positive quadratic non-residue modulo $p \geq 3$, that is, the smallest positive integer $r$ for which the congruence $x^2 \equiv r \enspace (\textrm{mod} \enspace p)$ has no solution. Prove that r is a prime number.

Any help is appreciated. Thank you!

$\endgroup$
  • 1
    $\begingroup$ Think about $r$'s prime factorisation. $\endgroup$ – Lord Shark the Unknown Aug 19 at 4:05
5
$\begingroup$

Suppose for contradiction that $r$, the smallest positive non-residue of $p$ is not a prime number. Then $r$ is a composite number greater then $1$. That means that $r$ has two factors $s$ and $t$ such that $s<r$ and $s<t.$ If $s$ and $t$ were both quadratic residues then $r$ would also be a quadratic residue. But $r$ is not a quadratic residue so either $s$ or $t$ must be a quadratic non-residue. Now we have found a positive non-residue mod $p$ that is smaller than $r$, which is a contradiction.

$\endgroup$
  • 1
    $\begingroup$ You should also rule out the possibility that $r=1$, since $1$ is not a prime but also does not factor into smaller parts. Sure, it’s very easy, but it should be mentioned. $\endgroup$ – Erick Wong Aug 19 at 4:26
  • $\begingroup$ That's a good point. $\endgroup$ – subrosar Aug 19 at 4:27
2
$\begingroup$

Assume neither $a$ nor $b$ are multiples of $p$.

$$(ab/p)=-1\rightarrow(a/p)(b/p)=-1$$

So if a composite number is a non-residue, it has a proper factor that is a non-residue. Therefore, the minimum non-residue must be prime.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.