 Solution

The eigenvalue on $|0⟩$ of every power is one, and its eigenvalue on $|1⟩$ is $e^{2\pi iak/N}$. ThusIf $a$ is odd, its greatest common divisor with $N=2^n$ is one. Divisibility can therefore be cancelled, givingIn particular, the $N$ powers with $0\le k<N$ are distinct. Each is the phase gate $R_m$ with $m\equiv ak(\mathrm{mod}N)$, and multiplication by $a$ is a permutation of these residue classes. Equivalently, for any desired $m$, choose $k\equiv a^{-1}m(\mathrm{mod}N)$, where $a^{-1}$ is the modular inverse. Then $R_a^k=R_m$, using the representative $0\le k<N$ and repeated forward applications only. Thus the powers generate the entire set. Once the preceding identification procedure has found $a$, these powers can also be labelled and selected classically.