Results 1 to 2 of 2

Thread: Equivalence class mod problem

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

    Equivalence class mod problem

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

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

    Proof so far.

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

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

    Is this correct? Thanks.
    Last edited by tttcomrader; Dec 8th 2008 at 04: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 $\displaystyle G = \frac { \mathbb {Q} } { \mathbb {Z} } $ under +, so the elements are the equivalence classes $\displaystyle \hat {r} = \{ s \in \mathbb {Q} : s-r \in \mathbb {Z} \} $. Write $\displaystyle r \equiv s \ (mod \ 1 ) $ if $\displaystyle r - s \in \mathbb {Z} $.

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

    To show that $\displaystyle \left< [\tfrac{a}{b}] \right> = \left< [\tfrac{1}{b}] \right>$ we will show $\displaystyle \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 $\displaystyle a( \tfrac{1}{b} ) = \tfrac{a}{b}$ and therefore $\displaystyle [ \tfrac{a}{b} ] \in \left< [ \tfrac{1}{b} ] \right>$

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

    To show that the order of $\displaystyle [\tfrac{1}{b}]$ is $\displaystyle b$ we need to find the smallest $\displaystyle k\in \mathbb{Z}^+$ such that $\displaystyle k[\tfrac{1}{b}] = [1] \implies [\tfrac{k}{b}] = [1]$.
    Say that $\displaystyle 0 < k < b$ with $\displaystyle d=\gcd(k,b)$ then $\displaystyle [\tfrac{k}{b}] = [ \tfrac{1}{b/d} ] \not = [1]$.
    Therefore the order is at least $\displaystyle b$. But if $\displaystyle k=b$ we get $\displaystyle b[ \tfrac{1}{b}] = [\tfrac{b}{b}]=[1]$.
    Thus, the order is $\displaystyle 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: Sep 30th 2009, 09:03 AM
  2. Equivalence Class
    Posted in the Differential Geometry Forum
    Replies: 3
    Last Post: Sep 22nd 2009, 05:51 AM
  3. Equivalence class
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: May 17th 2009, 08:45 AM
  4. help with equivalence class
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Dec 13th 2008, 11:32 PM
  5. Equivalence class problem
    Posted in the Advanced Algebra Forum
    Replies: 8
    Last Post: Jul 12th 2006, 08:24 PM

Search Tags


/mathhelpforum @mathhelpforum