# Thread: Equivalence class mod problem

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

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$.