Proving p Elts in $\mathbb{Z}_p$

[Kindayr]

Homework Statement

Fix an integer p>1. Prove that \mathbb Z_{p} has exactly p elements.

Homework Equations

Define the relation \equiv on \mathbb Z by setting a\equiv b iff p|b-a. (We have shown \equiv to be an equivalence relation on \mathbb Z). Let \mathbb Z_{p}=\{[a]:a\in\mathbb Z\}, where [a]=\{b\in\mathbb Z:a\equiv b\}.

The Attempt at a Solution

I've unsuccessfully tried to show that if it had less than p elements, then the union of the equivalence classes would not 'fill' \mathbb Z, and so \equiv would not partition \mathbb Z, and so it would not be an equivalence relation: a contradiction. But I just can't get there, and I feel that that is much more of a difficult way to go about, and that there is a much easier route, any ideas?

 

[micromass]

Maybe you can try to prove something stronger, namely that

\mathbb{Z}_p=\{[0],[1],...,[p-1]\}

So there are two things to prove here:
- If a\in \mathbb{Z}, then [a]= for 0\leq b\leq p-1.
- If 0\leq a,b\leq p-1 and if [a]=, then a=b

Do you agree that this is what you need to prove?

 

[Kindayr]

Yes I agree those two points prove what is necessary. I'll have a go:

Let a\in\mathbb Z. We know that a=np+r. Note that 0\leq r\leq p-1 (if i have to prove this I will). Then we have |r-a|=np\implies \frac{|r-a|}{p}=n\in\mathbb Z. So we have p|r-a, so a\in[r], as required.

Let 0\leq a,b\leq p-1 and suppose [a]= with a\neq b. Then we have p|b-a\implies |b-a|=np. Since a\neq b\implies0<|b-a|, it follows that 0<np\implies n\neq 0. This tells us that the distance between a and b is a non-zero integer multiple of p. Note a,b are interchangeable without loss of generality. We know 0\leq a\leq p-1 and b=np+a, so it follows that 0\leq a\leq p-1\implies np\leq a+np\leq np+p-1\implies p-1<np\leq b\leq (n+1)p-1, with n>0: a contradiction. (EDIT: Made stronger conclusion)

Does that work? Your hints gave me a lot of help, thank you for getting my mind off my previous proof.

 

[micromass]

That seems to work fine! Good job!