1
$\begingroup$

$a^n \equiv r \pmod p$

given $r, a, p$

$p$ is an odd prime

$p \equiv 3 \pmod 4$

Here, $a$ is a primitive root modulo $p$, so the first equation has a unique solution $0 \le n. It is easy to tell whether $n$ is even by Euler's criterion.

Is it possible to decide whether $n\equiv 0 \pmod 4$, without explicitly solving for $n$?

  • 1
    Given$a$QR $r$, for half of the primitive roots the answer is yes, for the other half it is no. But I have no ideas about how to tell which half (for $r$) the primitive root $a$ belongs to. There may be$a$connection with quadratic residues mod $p^2$.2012-06-21

1 Answers 1

1

$\rm\:p\equiv 3\pmod 4\:$ is simple for biquadratic residues. This goes back to Gauss, e.g. see Wikipedia.

If prime $\rm\: p\equiv 3 \pmod 4\:$ then every quadratic residue $\rm\:(mod\ p)\:$ is also a biquadratic residue. The first supplement of quadratic reciprocity states $−1$ is a quadratic nonresidue, so for any integer $\rm\:x,\:$ one of $\rm\:x\:$ and $\rm\:−x\:$ is a quadratic residue, and the other a nonresidue. Thus, if $\rm\:r \equiv a^2\pmod p\:$ is a quadratic residue, then if $\rm\:a\equiv b^2\:$ is a residue, $\rm\:r \equiv a^2\equiv b^4 $ is a biquadratic residue, and if $\rm\:a\:$ is a nonresidue, $\rm\:−a\:$ is a residue, $\rm\:−a\equiv b^2,\:$ and again, $\rm\:r \equiv (−a)^2 \equiv b^4\:$ is a biquadratic residue.

  • 0
    Agree that the current formulation is unnatural in the sense that the natural domain for the exponent $n$ is $\mathbb{Z}/(p-1)\mathbb{Z}$, and, as you explained, in that ring the cosets of even numbers are all multiples of 4 also.2012-06-21