1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

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

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    Maybe you can try to prove something stronger, namely that

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

    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

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    That seems to work fine!! Good job! :smile:
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook