First, think of what numbers Xi can possibly have a gcd with m that is equal to gcd(a,m). The easiest and first constraint to apply is that each Xi must be a multiple of gcd(a,m) — otherwise it wouldn't have all the necessary factors. After that, think of how we can make sure each Xi doesn't have too many factors. The first step is to divide the ok factors, gcd(a/m), out of our Xi and m. They become precisely the integers and m/gcd(a,m) respectively. Then the totient function solves.