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.

Let $p$ be a prime. I know, due to Euler's criterion, that if $x^2 \equiv -1 \pmod{p}$ is solvable, then $p \equiv 1 \pmod{4}$ simply because I inspect which $p$ that are such that $(-1)^\frac{p-1}{2} = 1$

However, when I am trying to "generalize" to $x^4 \equiv -1 \pmod{p}$, I fail to recognize for which $p$ this equation has a solution?

share|improve this question

1 Answer 1

up vote 6 down vote accepted

Beside the uninteresting $p=2$, these are all the primes of the form $8k+1$.

In general, if $\gcd(a,p)=1$, then the congruence $x^k\equiv a\pmod{p}$ has a solution if and only if $$a^{(p-1)/d}\equiv 1\pmod{p},$$ where $d=\gcd(k,p-1)$. The quickest argument uses a primitive root, that is, a generator of the multiplicative group modulo $p$.

share|improve this answer
    
A different way of phrasing the same argument might also be enlightening: the multiplicative group modulo $p$ is cyclic of order $p-1$. Therefore there is a solution to $x^4\equiv-1\pmod p$ if and only if there is a solution to $4n\equiv (p-1)/2\pmod{p-1}$. (The $-1$ turns into $(p-1)/2$ because both are the unique elements of order $2$ in their respective groups.) –  Greg Martin Feb 21 '13 at 20:59

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.