Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

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

1 Answer 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.

share|improve this answer
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<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
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). –  Bill Dubuque Jun 21 '12 at 18:33
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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