Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: 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
    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
    Seems ok!! Congratulations!! :smile:
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook