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,

so .