what you want to show is that the mapping

(j = 1,....,m) is not 1-1 if gcd(b,m) ≠ 1.

suppose that

, 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

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

clearly,

.

(if

is a multiple of m, surely

is as well).

however,

.

so

but

.

so since the map

is not 1-1, it cannot be onto (since our set of representatives is finite),

so

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