Tuesday, 22 July 2014

abstract algebra - Primitve roots and congruences?



Let p be an odd prime. Show that the congruence x41 (mod p)  has a solution if and only if p is of the form 8k+1.



Here is what I did



Suppose that x41 (mod p)  and let y=indrx. Then x is aolso a solution and indr(x) indr(1)+indr(x) (p1)/2+y(modp1) Without loss of generality, we may take $0
\equiv ind_r(p-1)/2(mod p-1) \text{ }\
.So4y = (p-1)/2+m(p1)$forsome$m$.But$4y<2(p1)$,so$4y=(p1)/2$andso$p=8y+1$or$4y=3(p1)/2$.Inthiscase,3mustdivide$y$,sowehave$p=8(y/3)+1$.Ineithercase,$p$isoftheform.Conversely,suppose$p=8k+1$andlet$r$beaprimitiverootof$p$.Take$x$$=$$rk$.Then$x4\equiv r^{4k} \text{ }\
\equiv r^{(p-1)/2} \text{ }\
\equiv -1 (mod p) \text{ }\
.Thisx$ is a solution.



We just learned some of this topic. My TA said do not worry about it yet. Is this correct?



Is there another way to do this? If so, please show me.


Answer




There is a simpler way:



If x^4\equiv-1\pmod p, x^8=(x^4)^2\equiv(-1)^2\pmod p\equiv1



So,ord_px must divide 8



But it can not divide 4 as x^4\equiv-1\pmod p\implies ord_px=8



Using this, 8 divides \phi(p)=p-1




Conversely seems to be fine in your approach


No comments:

Post a Comment

real analysis - How to find lim_{hrightarrow 0}frac{sin(ha)}{h}

How to find \lim_{h\rightarrow 0}\frac{\sin(ha)}{h} without lhopital rule? I know when I use lhopital I easy get $$ \lim_{h\rightarrow 0}...