# $a^n\pmod p = r$, given $r, p, a$, how to check if $n\pmod 4 = 0$?

$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<p$. 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$?

-
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 $n<p$? –  Erick Wong Jun 21 '12 at 16:45
Yes, only for $n<p$ –  Must Jun 21 '12 at 16:55
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. –  Jyrki Lahtonen Jun 21 '12 at 18:15
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$. –  André Nicolas Jun 21 '12 at 18:34

$\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.
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<p-1$. That is a very different question, because the answer depends on the choice of the primitive root. For example selecting $a=5$ in the above example changes the answer for some $r$. –  Jyrki Lahtonen Jun 21 '12 at 18:24
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. –  Jyrki Lahtonen Jun 21 '12 at 18:40