# Thread: Equivalence class mod problem

1. ## 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.

2. Originally Posted by tttcomrader
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$.