# Thread: Prime numbers and congruence equations.

1. ## Prime numbers and congruence equations.

Let p be a prime number, and k is a positive integer.

(a) Show that if x is an integer such that x^2 is congruent to x mod p, then x is congruent to 0 or 1 mod p.

(b) Show that if x is an integer such that x^2 is congruent to x mod p^k, then x is congruent to 0 or 1 mod p^k.

2. Originally Posted by DEUCSB
Let p be a prime number, and k is a positive integer.

(a) Show that if x is an integer such that x^2 is congruent to x mod p, then x is congruent to 0 or 1 mod p.

(b) Show that if x is an integer such that x^2 is congruent to x mod p^k, then x is congruent to 0 or 1 mod p^k.
Write them out in non-modulo form. For example, the first equation reads,

$\displaystyle x^2=x + pr$ for some $\displaystyle r \in \mathbb{Z}$. This gives you that $\displaystyle x(x-1) = pr$ and so $\displaystyle x \equiv 0 \text{ mod }p$ or $\displaystyle x-1 \equiv 0 \text{ mod }p$, as required.

The second one is approached similarly.