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'm still making my way along in Niven's Intro to Number Theory, and the title problem is giving me a little trouble near the end, and I was hoping someone could help get me through it.

Now $x^8\equiv 16\pmod{2}$ is solvable with $x\equiv 0\pmod{2}$, so I assume $p$ is an odd prime. From a theorem earlier in the text,

If $p$ is a prime and $(a,p)=1$, then the congruence $x^n\equiv a\pmod{p}$ has $(n,p-1)$ solutions or no solution according as $a^{(p-1)/(n,p-1)}\equiv 1\pmod{p}$ or not.

So since $(16,p)=1$, the problem reduces to showing that $16^{(p-1)/(8,p-1)}\equiv 1\pmod{p}$ holds for all $p$. I note that $(8,p-1)$ can only take values $2,4,8$. For $2$, the above equivalence is then $4^{p-1}\equiv 1\pmod{p}$, which is true by Fermat's little Theorem. For $4$, it is then $2^{p-1}\equiv 1\pmod{p}$, which again holds by FlT. However, the case where $(8,p-1)=8$ is throwing me off. At best I see that $16^{(p-1)/8}\equiv 2^{(p-1)/2}\pmod{p}$, but I'm not sure how to show this is congruent to $1$ modulo $p$. Maybe there's a more elegant way to do it without looking at cases. Thanks for any insight.

share|improve this question
    
This problem naturally splits into cases. Don't be afraid to think casewise. –  Qiaochu Yuan Oct 14 '10 at 9:56
1  
This problem played a role in the development of the Grunwald–Wang theorem; see en.wikipedia.org/wiki/Grunwald-Wang_theorem#History –  lhf Oct 17 '10 at 23:46
add comment

3 Answers

up vote 4 down vote accepted

One way is to use the Legendre symbol identity $2^{(p-1)/2} \equiv (\frac{2}{p}) \equiv (-1)^{(p^2-1)/8} \pmod p$ (for odd primes p), keeping in mind that if (8,p-1)=8 then $p \equiv 1 \pmod 8$.

share|improve this answer
    
Thanks, I overlooked that identity. I had a small question to add. I know if $a$ is a quadratic residue modulo $p$, then the Legendre symbol $(a|p)=1$ . However, if by some calculation I find that $(a|p)=1$, is it also the case that $a$ is a quadratic residue modulo $p$? –  yunone Oct 14 '10 at 10:13
    
Yep that's right (unless if a=0 (mod p)). –  Douglas S. Stones Oct 14 '10 at 21:22
add comment

HINT $\rm\ \ \ x^8 - 16\ =\ (x^2 - 2)\: (x^2 + 2)\: (x^4 + 4)\:.\ \:$ If the first two factors have no roots in $\rm\ \mathbb Z/p\ $ then $\:2, -2\:$ are nonsquares so their product $-4\: $ is a square, so $\rm\: i = \sqrt{-1} \in \mathbb Z/p\:$. Thus the third factor has a root since $\rm\ x^4 + 4\ $ has roots $\rm\: \pm 1\pm i\:$.

share|improve this answer
    
I'm only learning elementary number theory, so I'm not too familiar with this. Could you please explain how $-4$ being a square implies $i=\sqrt{-1}\in\mathbb{Z}/p$? –  yunone Oct 14 '10 at 23:27
    
If $j^2 \equiv -4$ then $(j/2)^2 \equiv -1$. Note: since p is odd, $1/2 \in \mathbb Z/p$, in fact $1/2 \equiv (p+1)/2$ –  Bill Dubuque Oct 14 '10 at 23:31
    
The quartic factors even further: $x^8 - 16 = (x^2+2)(x^2-2)(x^2+2x+2)(x^2-2x+2)$. The last two factors both have discriminant $-4$, so if neither 2 nor $-2$ is a square mod $p$ then $-1$ is and thus the last two factors both have roots mod $p$. –  KCd Oct 11 '11 at 2:35
add comment

I usually set this as an exercise when teaching Number Theory. My hint is to ask the students: what are the solutions of $z^8=16$ in the complex numbers?

share|improve this answer
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.