[Last Call] Learn how to a build a cloud-first strategyRegister Now

x
  • Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 227
  • Last Modified:

congruence prime power

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.)
0
AlephNought
Asked:
AlephNought
  • 2
  • 2
1 Solution
 
ozoCommented:
3^2 = 1 (mod 2^3)
0
 
AlephNoughtAuthor Commented:
What if we only consider forms with primitive roots, i.e. when p does not equal 2^k where k is greater than 2?
0
 
thehagmanCommented:
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.

0
 
ozoCommented:
x=±1 (mod p)
x=(np±1)
(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
0
 
AlephNoughtAuthor Commented:
Thanks! That was very helpful!
0

Featured Post

VIDEO: THE CONCERTO CLOUD FOR HEALTHCARE

Modern healthcare requires a modern cloud. View this brief video to understand how the Concerto Cloud for Healthcare can help your organization.

  • 2
  • 2
Tackle projects and never again get stuck behind a technical roadblock.
Join Now