1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Show -1 and +1 are only solutions to x^2 = 1 (mod p^2) for odd prime p.

  1. Oct 19, 2011 #1
    1. The problem statement, all variables and given/known data

    Let p be an odd prime and n be an integer. Show that -1 and +1 and the only solutions to [itex]x^2 \equiv 1\ mod\ p^n.[/itex] Hint: What does [itex]a \equiv b\ mod\ m[/itex] mean, then think a bit.


    2. Relevant equations

    [itex]x^2 \equiv 1\ mod\ p^n \rightarrow x^2 = 1 + p^nk[/itex] for k an integer.

    3. The attempt at a solution

    I've tried using the fact that [itex]x^2 \equiv 1\ mod\ p^n[/itex] implies that x is its own inverse and thus that [itex]x \equiv x\ mod\ p^n[/itex] and that [itex]x^2 \equiv 1\ mod\ p^n[/itex] implies [itex]x^2 \equiv 1\ mod\ p^{n-1}[/itex], attempting to find a way to combine the equations to force x to be either 1 or -1, but neither of these got me anywhere. The hint the teacher left makes me think the answer is something fairly simple (perhaps perfect squares cannot have the form [itex]x^2 = p^nk + 1[/itex] for [itex]p > 2[/itex]), but I just can't seem to see it. I have a feeling that just the tiniest push in the right direction would lead me to the answer.
     
  2. jcsd
  3. Oct 19, 2011 #2

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    If [itex]x^2=1[/itex] (mod [itex]p^n[/itex]), then [itex]p^n[/itex] divides [itex]x^2-1[/itex].

    Rewrite [itex]x^2-1[/itex].
     
  4. Oct 19, 2011 #3
    So, [itex]x^2 \equiv 1\ mod\ p^n[/itex] implies [itex]p^n|x^2 - 1[/itex].
    Factoring [itex]x^2 - 1[/itex], we have that [itex]p^n|(x+1)(x-1)[/itex].
    Since [itex](x + 1) - (x - 1) = 2[/itex], [itex]p^n|(x+1)[/itex] and [itex]p^n|(x-1)[/itex] only if [itex]p|2[/itex], which would imply that p=2. However, since we are dealing with odd primes, Euclid's Lemma requires that either [itex]p^n|(x+1)[/itex] or [itex]p^n|(x-1)[/itex]. For [itex]x\ mod\ p^n[/itex], the only solution to the first relation is [itex]x\ =\ p^n - 1 \equiv -1\ (mod p^n)[/itex], and the only solution to the second relation is [itex]x\ =\ 1 \equiv 1\ (mod p^n)[/itex]. Thus, [itex]x \equiv \pm 1\ (mod\ p^n)[/itex] are the only solutions to [itex]x^2 \equiv 1\ (mod\ p^n)[/itex] for p < 2.

    Is this correct?
     
    Last edited: Oct 19, 2011
  5. Oct 19, 2011 #4

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    Seems ok!! Congratulations!! :smile:
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook