Results 1 to 2 of 2

Thread: solvable congruent

  1. #1
    Super Member
    Joined
    Aug 2009
    Posts
    639

    solvable congruent

    How do you proof that -1 congruent to x^4 mod p is solvable iff (-1)^(p-1/d) is congruent to 1 mod p where d= gcd(4,p-1)?

    i was trying to use euler theorem that (-1)^(p-1) is congruent to 1 mod p then how else can i continue?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member Sylvia104's Avatar
    Joined
    Mar 2012
    From
    London, UK
    Posts
    107
    Thanks
    37

    Re: Solvable congruent

    I take it you want $\displaystyle p$ to be prime. The case $\displaystyle p=2$ is trivial, so we'll assume $\displaystyle p$ to be odd. Then $\displaystyle d=2$ if $\displaystyle p\equiv3\mod4$ and $\displaystyle d=4$ if $\displaystyle p\equiv1\mod 4.$


    If $\displaystyle p\equiv3\mod4$ then by Euler's criterion $\displaystyle \left(\frac{-1}p\right)=(-1)^{\frac{p-1}2}=-1.$ In this case $\displaystyle x$ is not a quadratic residue modulo $\displaystyle p$ (and so it certainly can't be a quartic residue modulo $\displaystyle p);$ we also have $\displaystyle (-1)^{\frac{p-1}d}=(-1)^{\frac{p-1}2}=-1\not\equiv1\mod p.$


    Consider $\displaystyle p\equiv1\mod4.$

    (i) Suppose $\displaystyle x^4\equiv-1\mod p.$ As $\displaystyle d=4$ in this case, $\displaystyle -1\equiv x^d\mod p$ $\displaystyle \implies$ $\displaystyle (-1)^{\frac{p-1}d}\equiv x^{p-1}\mod p\equiv1\mod p$ by Fermat's little theorem.

    (ii) Conversely suppose $\displaystyle (-1)^{\frac{p-1}d}=(-1)^{\frac{p-1}4}\equiv1\mod p.$ Then $\displaystyle \frac{p-1}4$ is even, i.e. $\displaystyle 8\mid p-1.$ Let $\displaystyle k$ be a primitive root $\displaystyle \mod p$ and set $\displaystyle x=k^{\frac{p-1}8}.$ Then $\displaystyle x^8\equiv1\mod p$ $\displaystyle \implies$ $\displaystyle p$ divides $\displaystyle x^8-1=\left(x^4+1\right)\left(x^4-1\right).$ But $\displaystyle p$ cannot divide $\displaystyle x^4-1$ otherwise $\displaystyle k^{\frac{p-1}2}\equiv1\mod p$ which would contradict the fact that, as a primitive root, $\displaystyle k$ has order $\displaystyle p-1$ in the multiplicative group of the integers modulo $\displaystyle p.$ Hence $\displaystyle p$ divides $\displaystyle x^4+1$ and we are done.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. solvable
    Posted in the Number Theory Forum
    Replies: 0
    Last Post: Apr 19th 2012, 08:29 AM
  2. S4 solvable
    Posted in the Advanced Algebra Forum
    Replies: 4
    Last Post: May 5th 2011, 10:46 PM
  3. solvable group
    Posted in the Advanced Algebra Forum
    Replies: 5
    Last Post: Jan 1st 2010, 09:44 AM
  4. solvable?
    Posted in the Business Math Forum
    Replies: 7
    Last Post: Nov 5th 2009, 07:54 PM
  5. Is this solvable?
    Posted in the Algebra Forum
    Replies: 0
    Last Post: Mar 11th 2009, 09:00 PM

Search Tags


/mathhelpforum @mathhelpforum