IMO 2007 — Complete Shortlist Question 25

Let $b, n\gt 1$ be integers. Suppose that for each $k\gt 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$.