Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Help with Z_p

  1. Aug 19, 2011 #1
    1. The problem statement, all variables and given/known data

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

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

    3. The attempt at a solution
    I've unsuccessfully tried to show that if it had less than [itex]p[/itex] elements, then the union of the equivalence classes would not 'fill' [itex]\mathbb Z[/itex], and so [itex]\equiv[/itex] would not partition [itex]\mathbb Z[/itex], 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?
  2. jcsd
  3. Aug 19, 2011 #2
    Maybe you can try to prove something stronger, namely that


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

    Do you agree that this is what you need to prove?
  4. Aug 19, 2011 #3
    Yes I agree those two points prove what is necessary. I'll have a go:

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

    Let [itex]0\leq a,b\leq p-1[/itex] and suppose [itex][a]=[/itex] with [itex]a\neq b[/itex]. Then we have [itex]p|b-a\implies |b-a|=np[/itex]. Since [itex]a\neq b\implies0<|b-a|[/itex], it follows that [itex]0<np\implies n\neq 0[/itex]. This tells us that the distance between [itex]a[/itex] and [itex]b[/itex] is a non-zero integer multiple of [itex]p[/itex]. Note [itex]a,b[/itex] are interchangeable without loss of generality. We know [itex]0\leq a\leq p-1[/itex] and [itex]b=np+a[/itex], so it follows that [tex]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,[/tex] with [itex]n>0[/itex]: 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.
    Last edited: Aug 19, 2011
  5. Aug 19, 2011 #4
    That seems to work fine!! Good job! :smile:
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook