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 [itex][a]=[/itex] 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!