Results 1 to 2 of 2

Math Help - Equivalence class mod problem

  1. #1
    Super Member
    Joined
    Mar 2006
    Posts
    705
    Thanks
    2

    Equivalence class mod problem

    Let G = \frac { \mathbb {Q} } { \mathbb {Z} } under +, so the elements are the equivalence classes  \hat {r} = \{ s \in \mathbb {Q} : s-r \in \mathbb {Z} \} . Write  r \equiv s \ (mod \ 1 ) if  r - s \in \mathbb {Z} .

    Prove that if r = \frac {a}{b} with a,b \in \mathbb {Z} ,  gcd (a,b) = 1 and b > 0 , then  \hat {r} has order b and  < \hat {r} > = < \hat { \frac {1}{b} } >

    Proof so far.

    So the operation here is addition,  \frac {a}{b} (b) = 1 , so would that prove the order is b?

    < \frac {1}{b} > = \{ \frac {1}{b}, \frac {2}{b}, \frac {3}{b}, ..., \frac {b}{b}=1 \} , which is the same as  < r >

    Is this correct? Thanks.
    Last edited by tttcomrader; December 8th 2008 at 05:53 PM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    Quote Originally Posted by tttcomrader View Post
    Let G = \frac { \mathbb {Q} } { \mathbb {Z} } under +, so the elements are the equivalence classes  \hat {r} = \{ s \in \mathbb {Q} : s-r \in \mathbb {Z} \} . Write  r \equiv s \ (mod \ 1 ) if  r - s \in \mathbb {Z} .

    Prove that if r = \frac {a}{b} with a,b \in \mathbb {Z} ,  gcd (a,b) = 1 and b > 0 , then  \hat {r} has order b and  < \hat {r} > = < \hat { \frac {1}{b} } >
    We will use [ r ] instead of \hat r.

    To show that \left< [\tfrac{a}{b}] \right> = \left< [\tfrac{1}{b}] \right> we will show \left< [\tfrac{a}{b}] \right> \subseteq \left< [\tfrac{1}{b}] \right> \text{ and }\left< [\tfrac{1}{b}] \right>\subseteq  \left< [\tfrac{a}{b}] \right>.

    The first inclusion follows because a( \tfrac{1}{b} ) = \tfrac{a}{b} and therefore [ \tfrac{a}{b} ] \in \left< [ \tfrac{1}{b} ] \right>

    For the second inclusion pick c\in \mathbb{Z} so that ac\equiv 1(\bmod b), this is possible because \gcd(a,b)=1.
    Then it follows that, c(\tfrac{a}{b}) = \tfrac{ac}{b} \equiv \tfrac{1}{b} and therefore [\tfrac{1}{b}] \in \left< [ \tfrac{a}{b} ] \right>.

    To show that the order of [\tfrac{1}{b}] is b we need to find the smallest k\in \mathbb{Z}^+ such that k[\tfrac{1}{b}] = [1] \implies [\tfrac{k}{b}] = [1].
    Say that 0 < k < b with d=\gcd(k,b) then [\tfrac{k}{b}] = [ \tfrac{1}{b/d} ] \not = [1].
    Therefore the order is at least b. But if k=b we get b[ \tfrac{1}{b}] = [\tfrac{b}{b}]=[1].
    Thus, the order is b.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Equivalence relation and order of each equivalence class
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: September 30th 2009, 10:03 AM
  2. Equivalence Class
    Posted in the Differential Geometry Forum
    Replies: 3
    Last Post: September 22nd 2009, 06:51 AM
  3. Equivalence class
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: May 17th 2009, 09:45 AM
  4. help with equivalence class
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: December 14th 2008, 12:32 AM
  5. Equivalence class problem
    Posted in the Advanced Algebra Forum
    Replies: 8
    Last Post: July 12th 2006, 09:24 PM

Search Tags


/mathhelpforum @mathhelpforum