1. Limited time only! Sign up for a free 30min personal 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!

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