congruence prime power

Posted on 2009-04-30
Last Modified: 2012-05-06
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.)
Question by:AlephNought
    LVL 84

    Expert Comment

    3^2 = 1 (mod 2^3)

    Author Comment

    What if we only consider forms with primitive roots, i.e. when p does not equal 2^k where k is greater than 2?
    LVL 20

    Accepted Solution

    Of course, if you know that all solutions to x^2 = 1 mod p^{k-1} are +1 and -1 mod p^{k-1} for some k>=2, then the only candidates for solutions of x^2 = 1 mod p^k are of the form x = a*p^{k-1} +- 1 with a in {0,1,...,p-1}.
    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.

    LVL 84

    Expert Comment

    x=±1 (mod p)
    (np±1)²=1 (mod p^k)
    (n²p² ± 2np + 1)=1 (mod p^k)
    np(np±2) =0 (mod p^k)
    (np)=p^k or p=2

    Author Closing Comment

    Thanks! That was very helpful!

    Write Comment

    Please enter a first name

    Please enter a last name

    We will never share this with anyone.

    Featured Post

    Why You Should Analyze Threat Actor TTPs

    After years of analyzing threat actor behavior, it’s become clear that at any given time there are specific tactics, techniques, and procedures (TTPs) that are particularly prevalent. By analyzing and understanding these TTPs, you can dramatically enhance your security program.

    Introduction On a scale of 1 to 10, how would you rate our Product? Many of us have answered that question time and time again. But only a few of us have had the pleasure of receiving a stack of the filled out surveys and being asked to do somethi…
    How to Win a Jar of Candy Corn: A Scientific Approach! I love mathematics. If you love mathematics also, you may enjoy this tip on how to use math to win your own jar of candy corn and to impress your friends. As I said, I love math, but I gu…
    Need more eyes on your posted question? Go ahead and follow the quick steps in this video to learn how to Request Attention to your question. *Log into your Experts Exchange account *Find the question you want to Request Attention for *Go to the e…
    Here's a very brief overview of the methods PRTG Network Monitor ( offers for monitoring bandwidth, to help you decide which methods you´d like to investigate in more detail.  The methods are covered in more detail in o…

    760 members asked questions and received personalized solutions in the past 7 days.

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

    Join & Ask a Question

    Need Help in Real-Time?

    Connect with top rated Experts

    9 Experts available now in Live!

    Get 1:1 Help Now