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.

I know that $-1$ is a square modulo $p$ iff $p\equiv 1\pmod{4}$. Curious about this, I'm trying to show that $-1$ is a fourth power if and only if $p\equiv 1\pmod{8}$, for $p$ odd.

I know that if $a^4\equiv -1\pmod{p}$ for some $a$, then $$ (-1)^{(p-1)/4}\equiv (a^4)^{(p-1)/4}\equiv a^{p-1}\equiv 1\pmod{p}. $$ So since $p$ is odd, $(-1)^{(p-1)/4}=1$, so $(p-1)/4$ is even, and thus $p\equiv 1\pmod{8}$.

How can the converse be shown? I was trying to break $(p-1)!$ into a power of $4$, by grouping the factors together without success. Thanks.

share|improve this question
add comment

2 Answers 2

up vote 3 down vote accepted

This is a direct consequence of the following more general result.

Theorem: Let $m$ be a positive integer that has a primitive root, and suppose that $\gcd(a,m)=1$. Then the congruence $x^k\equiv a\pmod{m}$ has a solution if and only if $$a^{\varphi(m)/\gcd(\varphi(m),k)}\equiv 1\pmod {m}.\tag{$1$}$$

To prove the result, let $g$ be a primitive root of $m$, and let $d=\gcd(\varphi(m),k)$. Taking indices with respect to $g$, we see that the congruence $x^k\equiv a\pmod{p}$ holds iff $$k\,\text{ind}\, x\equiv \text{ind}\,a \pmod{\varphi(m)}.\tag{$2$}$$

The linear congruence $(2)$ has a solution for $\text{ind}\,x$ iff $d$ divides $\text{ind}\, a$.

To complete the proof, we show that $(1)$ holds iff $d$ divides $\text{ind}\,a$.

By taking indices, we can see that $(1)$ is equivalent to $\frac{\varphi(m)}{d}\text{ind}\, a\equiv 0\pmod {\varphi(m)}$. This holds iff $d$ divides $\text{ind}\,a$.

share|improve this answer
    
Thanks André, what does it mean to "take indices?" –  Dedede Jan 2 '13 at 22:56
    
Let's take your case, $m=p$. Let $g$ be a primitive root of $p$. Let $b$ be relatively prime to $p$. Then since $g$ is a generator, there is a unique $k\lt p-1$ such that $b\equiv g^k \pmod{p}$. This $k$ is called the index of $b$. It behaves like the logarithm. "Take indices" means take the discrete logarithm of both sides. –  André Nicolas Jan 2 '13 at 23:06
    
I understand now. Thanks again! –  Dedede Jan 3 '13 at 17:02
add comment

You can also use the fact that the multiplicative group of a finite field is cyclic (not difficult to prove directly, but proofs can be found in many textbooks, for example "Topics in Algebra" by Herstein). Let $a$ be an element of (multiplicative) order $p-1$ in the field $\mathbb{Z}/p\mathbb{Z}$. Then if $p \equiv 1 $ (mod 8), we see that $b = a^{\frac{p-1}{8}}$ is an element of (multiplicative) order $8$ in $\mathbb{Z}/p\mathbb{Z}$. Then $c = b^{4}$ satisfies $c^{2} = 1 \neq c,$ and so $c = -1,$ which has also been expressed as the fourth power of $b.$

share|improve this answer
    
I'm aware of that result, but hadn't thought to use it like this. Very nice, thanks. –  Dedede Jan 3 '13 at 17:04
add comment

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.