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