the trick is to first prove .
now k = db, so therefore:
writing d = ns + kt (which we can by the euclidean algorithm), we have:
so we also know that
so . this means that .
now obviously . suppose that
for some 0 < u < n/d. then 0 < du < n, but
contradicting the fact that the order of g is n. thus there can be no such u,