1. ## Congruence Equations

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.

2. ## Re: Congruence Equations

Originally Posted by kinhew93
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.
Do you plan to show any of your efforts?

If ${x^2} \equiv x\left( {\bmod \,p} \right)$ then $x^2=kp+x$ Is that correct?

3. ## Re: Congruence Equations

Originally Posted by Plato
Do you plan to show any of your efforts?
If ${x^2} \equiv x\left( {\bmod \,p} \right)$ then $x^2=kp+x$ Is that correct?
Yeah that's right

My attempts are non existent, I really have no idea what to do

4. ## Re: Congruence Equations

Originally Posted by kinhew93
Yeah that's right. My attempts are non existent, I really have no idea what to do
So $x^2-x-kp=0$ Correct? Or $x=\dfrac{1\pm\sqrt{1+4kp}}{2}$

How would that be possible if $x$ is an integer ?

5. ## Re: Congruence Equations

Originally Posted by Plato
So $x^2-x-kp=0$ Correct? Or $x=\dfrac{1\pm\sqrt{1+4kp}}{2}$

How would that be possible if $x$ is an integer ?
]

So this can only happen when 4kp= 0 which gives x = 0 and 1.

How do you then get to 0 modp and 1 modp?

6. ## Re: Congruence Equations

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:

x2 - x in the polynomial ring Zp[x].

Since Zp is a field, we know it has no more than 2 roots in Zp.

Now:

x2 - x = 0 (mod p)

is the same as:

x(x - 1) = 0 (mod p)

which makes it evident that the only integers in Zp that are solutions are 0 (mod p) and 1 (mod p).

7. ## Re: Congruence Equations

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.