Solved

Posted on 2009-04-30

I know that the only solutions to x^2= 1 (mod p) are +1 and -1.

If I had the congruence x^2= 1 (mod p^k), would the only solutions to this also be +1 and -1? If so, why? (I was thinking maybe Hensel's lemma or the Chinese remainder theorem, but I can't convince myself.)

If I had the congruence x^2= 1 (mod p^k), would the only solutions to this also be +1 and -1? If so, why? (I was thinking maybe Hensel's lemma or the Chinese remainder theorem, but I can't convince myself.)

5 Comments

Then x^2 = a^2 * p^{2k-2} +- 2*a*p^{k-1} +1 = 1 mod p^k implies (since 2k-2 >= k) that +-2a*p^{k-1} = 0 mod p^k, i.e. 2a=0 mod p.

Hence by induction your assumnption is correct for all odd primes p.

ozo's comment indicates that the case p=2 is a bit different, thiough, since "2 is the oddest prime".

You cannot make use of the CRT, however, to conclude anything about composite p (not even for odd p).

Indeed, the CRT guarantees that e.g. there is x with x^2 = 1 mod 15 having x=+1 mod 3 and x=-1 mod 5, hence not x=+-1 mod 15 (namely: x=4)

Primitive roots don't help either: If p = 2*q^m with q an odd prime and m>0, then the only solutions of x^2=1 mod p are x=+-1 (by CRT), but x^2 = 1 mod p^3 also has solutions with x=3 mod 8 or x=5 mod 8.

By clicking you are agreeing to Experts Exchange's Terms of Use.

Title | # Comments | Views | Activity |
---|---|---|---|

Excel - Average versus AverageA = Why use AverageA? | 2 | 52 | |

invest money into checking/savings account | 4 | 84 | |

Relative Frequency Assessment | 2 | 21 | |

Dice Roll Probabilities | 3 | 30 |

Join the community of 500,000 technology professionals and ask your questions.

Connect with top rated Experts

**9** Experts available now in Live!