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$.
up vote 11 down vote accepted

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 :-)

  • In fact, it's enough to assume that the integer is an $n$th power modulo almost all primes, if I remember correctly. – Arturo Magidin Oct 16 '10 at 21:17
  • 2
    @Arturo: usually, but not always. Please see the wikipedia article on Grunwald-Wang linked to below. – Pete L. Clark Oct 17 '10 at 4:35
  • 1) The first claim seems to be wrong : $x^8-16$ has roots mod $p$ for every prime $p$, but not in $\Bbb Z$ (nor modulo $32$) $$ $$ 2) This argument when $n$ is prime implies the result when $n$ is square-free, since an integer being an $a$-th power and a $b$-th power is an $ab$-th power whenever $a$ and $b$ are coprime. $$ $$ 3) For squares, it's enough to assume for a set of primes of density $>1/2$, see math.stackexchange.com/questions/80419. – Watson Nov 5 at 15:42

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

For any prime $p$, 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$.

Assume for the sake of contradiction that $r_p$ is not divisible by $n$. Let $[z]$ denote the least integer greater than $z$, where $z$ is real. Since $p^{r_p}$ divides $a_k^n$, $p^{[r_p/n]}$ divides $a_k$, so since $n \cdot [r_p/n]>r_p$, $n \cdot [r_p/n]\ge r_p+1$. Then, $k=p^{r_p+1}$ divides $p^{n \cdot [r_p/n]}$ which divides $a_k^n$, so $k$ divides $x$, which contradicts the maximality of $r_p$.

Thus, for all $p$, $n$ divides $r_p$, so $x$ is an $n$th power.

  • "(If $r_p$ is not divisible by $n$) then $k=p^{r_p+1}$ divides $a_k^n$" -- why, actually? – Grigory M Nov 4 '12 at 10:00
  • I added more details to the above proof to answer your question. – Eric Schneider Nov 8 '12 at 20:30
  • Looks like it actually works. Nice! – Grigory M Nov 9 '12 at 18:51
  • I so enjoy seeing a "difficult theorem" proven with such elegance. Lovely work! – Kieren MacMillan Oct 4 '14 at 1:06
  • @KierenMacMillan One can give even shorter elementary proofs, e.g. see my answer here. – Bill Dubuque Jul 3 '16 at 17:52

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.)

  • I'm not exactly sure if invoking the $p$-adic integers and their valuation is something that can really be called "elementary"; of course, in fairness you said "more elementary"; perhaps like K2 is "lower than" Everest... (-: – Arturo Magidin Oct 17 '10 at 4:19
  • 1
    @Arturo: right, I said "more elementary", as in more elementary than deep global results like Chebotarev density, Grunwald-Wang or even Dirichlet's theorem. – Pete L. Clark Oct 17 '10 at 4:32
  • very nice! It looks like Step 3 uses a stronger hypothesis than Robin and I were using (divisibility by prime powers instead of primes). – Qiaochu Yuan Oct 18 '10 at 23:47
  • 3
    @Arturo : I think the above proof would look much easier if you take into account the fact that step 1 could be skipped, step 3 is essentially the definition of $\mathbb{Z}_p$ and step 4 is the additivity of the $p$-adic valuations. None of these facts require much knowledge about $p$-adic integers beyond their definition (as an inverse limit). – Joel Cohen May 6 '11 at 22:13
  • @PeteL.Clark In fact one can go even more elementary, e.g. see my answer. – Bill Dubuque Jul 3 '16 at 17:57

To be a little more concrete, here's the proof for $n = 2$. We proceed by proving the contrapositive. Suppose $x$ is not a square, so write $x = k^2 p_1 p_2 ... p_n$ where the $p_i$ are distinct primes, one of which may be $-1$. By quadratic reciprocity, together with the CRT, there exists an arithmetic progression such that any prime $q$ in that arithmetic progression has the property that $\left( \frac{p_i}{q} \right) = 1$ for $1 \le i \le n-1$ and $\left( \frac{p_i}{q} \right) = -1$ for $i = n$. A prime $q$ exists in this arithmetic progression by Dirichlet's theorem (a special case of Chebotarev's density theorem!), and $x$ is not a square $\bmod q$.

Similarly for $n = 3$ one can give a proof using cubic reciprocity, and so on. In general it should be possible to give a proof along these lines using Artin reciprocity, but if you're using Artin reciprocity and Dirichlet's theorem you might as well use the full strength of Chebotarev.

  • 2
    This approach appears in second page of Marshall Hall, "Quadratic residues in factorization", Bull. Amer. Math. Soc. 39 (1933), no. 10, 758–763. doi – lhf Apr 18 '11 at 18:42

$x^2\mid x-a^n\Rightarrow\, x\mid a^n\,$ so $\ \color{#c00}{ a^n = kx}\ $ and $\ jx^2\! = x-\!\overbrace{kx}^{\large\ a^n} $ for some integers $\,j,k.\,$ Notice $\,k = 1-jx\,$ is coprime to $\,x,\,$ thus, like $\,\color{#c00}{a^n},\,$ it follows that $\,\color{#c00}k\,$ and $\,\color{#c00}x\,$ are $\,n$'th powers too.

  • The proof generalizes to the case where $x$ is a factor of $a^n$ with coprime cofactor, i.e. $\,k\mid c_k x-a_k^n\,$ for coprime $\,c_k,x,\,$ i.e. the modular analog of the linked theorem. – Bill Dubuque Jul 3 '16 at 18:06
  • How do you get the very first item $x^2 \mid (x-a^n)$? After that, I'm fine… – Kieren MacMillan Jul 11 '16 at 17:59
  • 1
    @Kieren Choose $\,k = x^2$ in the hypothesis. $\ $ – Bill Dubuque Jul 11 '16 at 18:45
  • Of course. Sorry/thanks. – Kieren MacMillan Jul 11 '16 at 20:50

Your Answer


By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.