ISL 2007 N2

Let $b, n>1$ be integers. Suppose that for each $k>1$ there exists an integer $a_{k}$ such that $b-a_{k}^{n}$ is divisible by $k$. Prove that $b=A^{n}$ for some integer $A$. (Canada)