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

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

  • 1
    Actually, it is impossible to determine if $n \equiv 0 \pmod 4$, even after solving to find $n$. If $n$ is a solution, then so is $n+p-1$. Do you mean to restrict $n2012-06-21
  • 0
    Yes, only for $n2012-06-21
  • 1
    It may be my limitation, but I'm a bit pessimistic here. The reason is that, unlike in the case when you want to determine whether $2\mid n$, the answer depends on the choice of $a$. For example replacing $a$ with its inverse modulo $p$ will replace $n$ with $(p-1)-n$ and a problem analogous to the one described by Erick Wong. Of course, if we had $p\equiv 1\pmod 4$, then we would simply check whether $r^{(p-1)/4}\equiv 1\pmod p$ or not.2012-06-21
  • 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.

  • 1
    This is all true, but judging from the comments, the OP is asking, whether for example in the case $p=7$, $a=3$ the number $r$ belongs to the set $\{a^0,a^4\}$. IOW the question is not about biquadratic residues, because the exponent $n$ is limited to the interval $0\le n$a=5$ in the above example changes the answer for some $r$. – 2012-06-21
  • 1
    @Jyrki Ah, I missed the comment. But I'll leave the answer because I think the OP may find the Wikipedia page on biquadratic residues very helpful (and, perhaps after learning more about such, the OP may rephrase the question more naturally).2012-06-21
  • 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