Let p be a prime and k a positive integer.
(a) Show that if x is an integer such that x^2=x mod p, then x= 0 or 1 mod p.
(b) Show that if x is an integer such that x^2=x mod p^k, then x= 0 or 1 mod p^k.
(c) Show that if p is odd and x is an integer such that x^2=1 mod p^k, then x= +/- 1 mod p^k.
(d) Find the solutions of the congruence equation x^2=1 mod 2^k.
Have looked at this for ages and can't get anywhere - any help would be much appreciated.
Not it is NOT true that it can "only happen when 4kp = 0". For example suppose p = 3. We could take k = 2, so that 4kp = 24, and then 1 + 4kp = 25, which is a perfect odd square, so we get x = 3 (which is 0 mod 3) or x = -2 (which is 1 mod 3).
Here is what I would do:
The integers mod p form a field, so we can form the polynomial:
x^{2} - x in the polynomial ring Z_{p}[x].
Since Z_{p} is a field, we know it has no more than 2 roots in Z_{p}.
Now:
x^{2} - x = 0 (mod p)
is the same as:
x(x - 1) = 0 (mod p)
which makes it evident that the only integers in Z_{p} that are solutions are 0 (mod p) and 1 (mod p).
Hi,
You need to know a few facts from elementary number theory. The attachments explicitly state these facts; you can prove them for yourself, look up the proofs or as a last resort ask me. Also shown are solutions to the first 3 problems. I give you the answer to number 4, but I've left the proof to you. If you have trouble, post again and I'll try and help.