An integer is an $n$th power if that holds true for all moduli

I have not been able to solve this problem. Any insights would be appreciated!

Let $x, n > 1$ be integers. Suppose that for each $k > 1$ there exists an integer $a_{k}$ such that $x − a_k^n$ is divisible by $k$. Prove that $x = A^{n}$ for some integer $A$.

Am I mistaken, or does the following (actually) elementary proof work?

To show that $x$ is a perfect $n$th power, it suffices to show that for all primes $p$, the number of times that $p$ divides into $x$ is a multiple of $n$.

To that end, fix any prime $p$, and let $r_p$ be the largest integer such that $p^{r_p}$ divides $x$. Consider $k=p^{r_p+1}$. Then, since $k$ divides $a_k^n -x$, $p^{r_p}$ divides $a_k^n$.

Moreover, it cannot be that $k = p^{r_p + 1}$ divides $a_k^n$. If it were so, then since $p^{r_p + 1}$ divides $a_k^n - x$, $p^{r_p + 1}$ would divide $x$, which contradicts the maximality of $r_p$.

Therefore, $p^{r_p}$ divides $a_k^n$ but $p^{r_p + 1}$ does not; it follows that $r_p$ is equal to the number of times $p$ divides into $a_k^n$, which must be a multiple of $n$ (consider the prime factorization of $a_k^n$), so we are done.

This is an old chestnut: an integer which is an $n$-th power modulo all primes is an $n$-th power.

There is a sledgehammer proof via the Chebotarev density theorem. Suppose for the moment that $n$ is prime. Consider $K=\mathbb{Q}(x^{1/n})$ and its Galois closure $L=\mathbb{Q}(x^{1/n},\exp(2\pi i/n))$. Then each prime $p$ that is unramified in $L$ splits in $K$ into various prime ideals at least one of which has norm $p$. So its Frobenius has a fixed point on the permutation representation on the $n$-th roots of $x$. By Chebotarev, the Galois group $G$ of $L/\mathbb{Q}$ has no element of degree $n$ and so must have a fixed point; that is one of the $n$-th roots of $x$ must lie in $\mathbb{Q}$.

I'm sure something similar works for any positive integer $n$, but it's too late tonight for me to work out the details :-)

I discovered this question 6 years later. Worth emphasis: there is a much simpler proof, namely choose $\,k^{\phantom{|^{|^|}}}\!\!\!=x^2\Rightarrow\,x^2\mid x-a^n\Rightarrow\, x\mid a^n\,$ so $\ \color{#c00}{ a^n\! = mx}\ $ so ${\ jx^2\! = x-\!\overbrace{mx}^{\large\ a^n}}^{\phantom{|}} $ for some $\,j,m\in\Bbb Z.\,$ Note $\,m = 1\!-\!jx\,$ is coprime to $\,x\,$ so, like $\,\color{#c00}{a^n}\,$ both $\color{#c00}{m\ \&\ x}^{\phantom{|^{|^|}}}\!\!\!\!\ $ must be $\,n$'th powers too.

If I am not mistaken, the question has a more elementary answer than those provided so far. I will use the functions $\operatorname{ord}_p: \mathbb{Q}^{\times} \rightarrow \mathbb{Z}$, defined to be the largest power of $p$ appearing in the numerator minus the largest power of $p$ appearing in the denominator.

Step 1: A positive rational number $x$ is a rational $n$th power iff for all primes $p$, $\operatorname{ord}_p(x)$ is divisible by $n$.

This is an easy consequence of unique factorization in $\mathbb{Z}$.

Step 2: A positive integer $x$ is an integral $n$th power iff for all primes $p$, $\operatorname{ord}_p(x)$ is divisible by $n$.

This follows easily from Step 1 using the fact that since $\mathbb{Z}$ is a UFD, it is integrally closed. (Alternately, apply the rational roots theorem to the polynomial $t^n - x$.)

Step 3: As in lhf's comment above, I claim that the given condition on $x$ implies that $x$ is an nth power in $\mathbb{Q}_p$ for all primes $p$. Indeed, taking $k$ to be a prime power, it implies that for all positive integers $a$, the congruence $t^n -x \equiv 0 \pmod{p^a}$ has a solution, and by a routine application of Hensel's Lemma, this implies that $x$ is an $n$th power in $\mathbb{Q}_p$.

Step 4: Since $x$ is an $n$th power in $\mathbb{Q}_p$, the $p$-adic valuation $v_p(x)$ is divisible by $n$. For a rational number $x$, this means that $\operatorname{ord}_p(x)$ is divisible by $n$. And we are done.

As regards the fancy stuff, perhaps people are thinking of the Grunwald-Wang Theorem.

This says that if $x$ is an element of a global field $K$ which is an $n$th power in all but finitely many completions at finite places $v$. Actually, this is "Grunwald's theorem", i.e., it isn't quite true! Wang showed that there are counterexamples to this statement, even over $\mathbb{Q}$ (if one uses all but finitely many places, rather than all places): see the wikipedia article for an explanation. The easy proof that I give above works in any global field which is the fraction field of a PID $R$, with the conclusion that $x$ comes out to be an $n$th power up to a unit of $R$. (When $R = \mathbb{Z}$, requiring $x$ to be positive fixes the unit ambiguity.)