3
$\begingroup$

It seems that every root of $-1$ quadratic residue modulo $p$ prime, $p = 1 \pmod 4$ is distinct.

I mean if $x$ is a root of $-1$ quadratic residue modulo $p$, then there is no other prime $q$ such $x$ is a root of $-1$ quadratic residue modulo $q$.

Is it correct, and if it is, how can it be demonstrated ?

Best regards.

$\endgroup$
  • 3
    $\begingroup$ How many prime factors $> n$ can $n^2+1$ have? $\endgroup$ – Daniel Fischer Dec 20 '16 at 11:07
  • $\begingroup$ I tested for every primes < 611953 $\endgroup$ – BenLaz Dec 20 '16 at 11:09
  • 2
    $\begingroup$ Depends on what qualifies as distinct for you. Remember that it is a bit problematic to say that a residue class modulo prime $p_1$ is distinct from a residue class modulo another prime $p_2$. By Chinese remainder theorem they intersect non-trivially. For example, $x=30$ is a square root of $-1$ modulo both $p_1=17$ and $p_2=53$. If you look at integers (as opposed to IMHO slightly more natural residue classes), and place the constraint $0<x<p$, then you can use Daniel's comment to conclude that... $\endgroup$ – Jyrki Lahtonen Dec 20 '16 at 11:12
  • $\begingroup$ Daniel Fischer : Obviously one, my question was "dumb", so I edit it. $\endgroup$ – BenLaz Dec 20 '16 at 11:15
4
$\begingroup$

This is true, provided that the specific root is in the range $\{ 1, \dots , p-1\}$. In other words: let $a$ be a root of $-1$ mod $p$ and mod $q$ with the conditions $0<a<p$, $0<a<q$. Then necessarily $p=q$.

Indeed, suppose by contradiction that $p\neq q$. If $a^2+1 \equiv 0 \pmod{p}$ and $a^2+1 \equiv 0 \pmod{q}$, then $pq$ divides $a^2+1$. In particular we have $pq \le a^2+1$. But now, $$a^2 \le (p-1)(q-1)=pq -(p+q-1) \le a^2+1-(p+q-1) =$$$$ = a^2- (p-1)-(q-1) \le a^2-2a $$ and this implies the contradiction $a \le 0$.

But without our condition, then this is false. For example for $a=8$ we have $a^2+1=65= 5 \cdot 13$, so that $8$ is a square root of $-1$ both mod $5$ and mod $13$. The problem here is that $8 \mod{5}=3$, so $8$ is "hidden behind" $3$.

$\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.