You're circling around the right ideas I think for 6.21. Going back to Dr. Wang's $a^k  = mq + r$ doesn't that mean that $a^k - mq = r$. If $\text{gcd}(a,m) > 1$, couldn't we factor this out of the left-hand side so that $r$ is actually a multiple of $\text{gcd}(a,m)$?