$a^k \mid b^k\ (\textrm{mod}\ m) \implies \exists n\forall r [b^k = na^k + rm]$
$a \mid b\ (\textrm{mod}\ m) \implies \exists s\forall r [b = sa + rm]$
$b^k = na^k + rm \implies (sa + rm)^k = na^k + rm \implies s^ka^k + m (1 + (sa)^{k-1}r + (sa)^{k-2}r^2m + \cdots + r^km^{k-1}) = na^k + rm \implies s^ka^k + m\Bbb{Z} = na^k + m\Bbb{Z} \implies s^k = n$