# Thread: Representatives of classes theorem

1. ## Representatives of classes theorem

Suppose {a1, a2,......, am} is a complete set of representatives for Z/mZ

Show if gcd(b, m) > 1, then {ba1, ba2, ......, bam} is not a complete set of representatives.

So far I have
[a]m ≡ [n]m
[ba]m ≡ [bn]m ≠ [n]m

not sure if this constitutes much of a proof though.

2. ## Re: Representatives of classes theorem

Originally Posted by scruz10
Suppose {a1, a2,......, am} is a complete set of representatives for Z/mZ

Show if gcd(b, m) > 1, then {ba1, ba2, ......, bam} is not a complete set of representatives.

So far I have
[a]m ≡ [n]m
[ba]m ≡ [bn]m ≠ [n]m

not sure if this constitutes much of a proof though.
This basically comes down to the fact that a number $0\leq i generates $\mathbb{Z}/m\mathbb{Z}$ if and only if $gcd(m, i)=1$. (Hint: use the Euclidean algorithm).

Can you see how your result follows from this?

3. ## Re: Representatives of classes theorem

That's pretty much what I have to prove. I already proved the first part where gcd(b,m)=1. I just don't know how to prove it is not a full set if it is greater than 11

Assume
[ba]m ≡ [bn]m ≡ [n]m
bn - n = mx
n(b - 1) = mx
b - 1 = mx/n
b - mx/n = 1
Therefore (b,m) = 1
Contradiction!
only thing is I can't tell if x/n is an integer.

4. ## Re: Representatives of classes theorem

Originally Posted by scruz10
That's pretty much what I have to prove. I already proved the first part where gcd(b,m)=1. I just don't know how to prove it is not a full set if it is greater than 11

Assume
[ba]m ≡ [bn]m ≡ [n]m
bn - n = mx
n(b - 1) = mx
b - 1 = mx/n
b - mx/n = 1
Therefore (b,m) = 1
Contradiction!
only thing is I can't tell if x/n is an integer.
Assume it is a full set, then you have that $ba_i + cm=1$ for some $i$ and some $c\in \mathbb{Z}$ (by the definition of modulus), so...

5. ## Re: Representatives of classes theorem

what you want to show is that the mapping $[a_j]\to [ba_j]$ (j = 1,....,m) is not 1-1 if gcd(b,m) ≠ 1.

suppose that $[0] = [m] = [a_s]$, and let gcd(b,m) = d > 1.

since d divides m, there is some 1 ≤ u < m with du = m (we are using the fact that d > 1 here).

note that [u] ≠ [m]. we'll use this later.

since d divides b, there is some integer v with dv = b. let $[a_t] = [u]$

(we can do this because we have a complete set of representatives, so u is in one of them).

clearly, $[ba_s] = [b][a_s] = [b][0] = [0b] = [0]$.

(if $a_s$ is a multiple of m, surely $ba_s$ is as well).

however, $[ba_t] = [b][a_t] = [b][u] = [bu] = [(dv)u] = [v(du)]$

$= [vm] = [v][m] = [v][0] = [0v] = [0]$.

so $[ba_s] = [ba_t]$ but $[a_s] \neq [a_t]$.

so since the map $[a_j]\to [ba_j]$ is not 1-1, it cannot be onto (since our set of representatives is finite),

so $\{ba_1,ba_2,\dots ,ba_m\}$ is not a complete set of representatives.

(i'm not usually so fussy about the brackets, but since the aj are presumably numbers, i use the brackets to indicate the entire equivalence class. hopefully you understand already that multiplication is well-defined on the equivalence classes, that is, that [a][b] = [ab], no matter "which" representatives we choose).

6. ## Re: Representatives of classes theorem

Originally Posted by Deveno
what you want to show is that the mapping $[a_j]\to [ba_j]$ (j = 1,....,m) is not 1-1 if gcd(b,m) ≠ 1.

suppose that $[0] = [m] = [a_s]$, and let gcd(b,m) = d > 1.

since d divides m, there is some 1 ≤ u < m with du = m (we are using the fact that d > 1 here).

note that [u] ≠ [m]. we'll use this later.

since d divides b, there is some integer v with dv = b. let $[a_t] = [u]$

(we can do this because we have a complete set of representatives, so u is in one of them).

clearly, $[ba_s] = [b][a_s] = [b][0] = [0b] = [0]$.

(if $a_s$ is a multiple of m, surely $ba_s$ is as well).

however, $[ba_t] = [b][a_t] = [b][u] = [bu] = [(dv)u] = [v(du)]$

$= [vm] = [v][m] = [v][0] = [0v] = [0]$.

so $[ba_s] = [ba_t]$ but $[a_s] \neq [a_t]$.

so since the map $[a_j]\to [ba_j]$ is not 1-1, it cannot be onto (since our set of representatives is finite),

so $\{ba_1,ba_2,\dots ,ba_m\}$ is not a complete set of representatives.

(i'm not usually so fussy about the brackets, but since the aj are presumably numbers, i use the brackets to indicate the entire equivalence class. hopefully you understand already that multiplication is well-defined on the equivalence classes, that is, that [a][b] = [ab], no matter "which" representatives we choose).
Seriously awesome....thanks