# Proving that an integer is the $n$ th power

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$.
• I changed this to what I think you meant. – Robin Chapman Oct 16 '10 at 20:45
• Is this what you meant to say? 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$. – Ross Millikan Oct 16 '10 at 20:49
• In fancy language: if $x$ is locally an $n$-th power, then $x$ is globally an $n$-th power. This is a (sucessful) instance of Hasse's local-global principle: en.wikipedia.org/wiki/Hasse_principle – lhf Oct 16 '10 at 21:04
• See also math.stackexchange.com/questions/6758/… which shows that solvability for all primes is not enough. A complete solution is in "A Conjecture of Chowla" by Ankeny and Rogers: jstor.org/stable/1969571 – lhf Oct 18 '10 at 1:12
• This is IMO Shortlist 2007, Problem N2. imo-official.org/problems/IMO2007SL.pdf – Evan Chen Dec 17 '15 at 7:02

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
• @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 '18 at 15:42

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.

• "(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
• @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
• @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

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.

• 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

Choose $$\,k=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}$$ for some integers $$\,j,m.\,$$ Notice $$\,m = 1-jx\,$$ is coprime to $$\,x,\,$$ so like $$\,\color{#c00}{a^n,\ m\ \&\ x}\,$$ must be $$\,n$$'th powers too.

• This is absolutely beautiful! – Vincent Feb 23 at 22:15
• @Vincent These simple beautiful methods essentially go back to Fermat's method of infinite descent - see Weil's remark here. – Bill Dubuque Feb 23 at 22:37
• Agree, very nice proof. – 6005 Sep 16 at 1:42