i believe the paper you are reading is incorrect. although U(36) has φ(36) = 12 elements, it is of exponent 6, meaning the 6-th residues are all trivial.

of course the next n to try would be 15, and U(225) has 120 elements, which is a bit more work than i'm prepared to go through, at the moment.