Let $x_1,\dots,x_k\geq1$ be fixed integers. Does there always exist an integer $m \ge 1$ so that $$x_1^{a_1}+\dots+x_k^{a_k}\equiv 0 \pmod{m}$$ has no solution for integers $a_1,\dots,a_k\geq0$?

The following proves the affirmative if $x_1=\ldots=x_k=:x$.

Assume without loss of generality $x\geq2$. Consider the modulus $m=x^\ell-1$. Let $k\geq1$ be the minimum number such that $x^{a_1}+\dots+x^{a_k}\equiv0$ has a solution modulo $m$. Since $x^\ell\equiv1\ (\mbox{mod}\ m)$, we can take the $a_i$ values modulo $\ell$. If $x$ of the $a_i$ values are equal, then they could have been replaced with a single $a_i$ value that is one larger. So every $a_i$ value appears at most $x-1$ times, giving $x^{a_1}+\dots+x^{a_k}\equiv c_0+c_1x+\dots+c_{\ell-1}x^{\ell-1}\equiv0$ for some $c_0,\dots,c_{\ell-1}\leq x-1$ summing to $k\geq1$. We find the only solution is $c_0=\ldots=c_{\ell-1}=x-1$ giving $k=\ell(x-1)$. Thus, if $k<\ell(x-1)$ then there is no solution.

If there is some prime $p$ that divides all $x_i$ but one, then there is no solution modulo $p$. So if $k=2$ then we can assume without loss of generality that $\mbox{rad}(x_1)=\mbox{rad}(x_2)=:r$. The following uses this to prove the affirmative if $k=2$.

If we assume $m\equiv7\ (\mbox{mod}\ 8)$, then $2$ is a quadratic residue modulo $m$ and $-1$ is not. Due to the Chinese remainder theorem, we can furthermore assume that $m$ is not a quadratic residue modulo all odd primes $p|r$. Due to Dirichlet's prime number theorem on arithmetic progression we can furthermore assume that $m$ is prime. By the law of quadratic reciprocity, it follows that all odd primes $p|r$ are quadratic residues modulo $m$. It follows that $x_1^{a_1}\equiv-x_2^{a_2}$ has no solution modulo $m$, having a quadratic residue on the left hand side but not the right hand side.

To give a bit of context, I saw a video about the equation $2^a+2^b=n!$. I decided to generalize this to $x^{a_1}+\dots+x^{a_k}=n!$ and proved it always has finitely many solutions by showing there exists $m$ such that $x^{a_1}+\dots+x^{a_k}$ is never divisible by $m$.

As a bonus, I was also wondering if the equation $$1^{a_1}+\dots+n^{a_n}=n!$$ has a solution for infinitely many values of $n$. This is probably highly non-trivial, for example with $n=6$ we find $1^1+2^3+4^1+3^4+5^4+6^0=6!$. Solving this is not necessary to get your answer accepted, but I am thinking of giving a bounty if you do solve it, depending on how hard it was.

  • $\begingroup$ $x \geq 2$ does lose some generality. But you can just cover the case $x = 1$ separately, with just $m=k+1$. $\endgroup$
    – aschepler
    May 7, 2022 at 23:46
  • $\begingroup$ Perhaps I abused the phrase wlog. I just wanted to omit the trivial case really :P $\endgroup$ May 7, 2022 at 23:56
  • $\begingroup$ I did some experimenting for $k=3$ and I always find a modulus for which there is no solution, but I was not able to find any patterns. However for $(x_1,x_2,x_3,x_4)=(2,2,3,3)$ I was not able to find any such modulus, so this could be a counterexample. $\endgroup$ May 23, 2022 at 22:30

1 Answer 1


Not an answer; too long for a comment.

The answer is nearly certainly "no", with $(x_1,x_2,x_3,x_4) := (2,2,3,3)$ possibly a counterexample, but a (dis)proof might be hard and/or even currently 'out of reach'.

We'll focus on 'large enough' $m$, since a counterexample for large enough $m$ easily yields a counterexample for all $m$ (by appending some more $x_j$'s).

Let $\ell,r \ge 1$ be some parameters, think $\ell,r=100$. Let $p_1,\dots,p_r$ be the first $r$ primes. Let $k = \ell r$ and let $(x_j)_{j=1}^k = (p_1,\dots,p_1,p_2,\dots,p_2,\dots,p_r,\dots,p_r)$, with each $p_i$ appearing $\ell$ times. We claim this is very likely a counterexample for large enough $m$.

Take $m \ge 1$ large (say $m \ge \exp(\ell^2+r^2)$). Let's start by assuming $m$ is prime; we'll discuss general $m$ later.

For $i=1,\dots,r$, let $S_i = \{p_i^a : 0 \le a \le m-1\}$ denote the powers of $p_i$ modulo $m$. Note that each $S_i$ is a multiplicative subgroup of $\mathbb{Z}_m$. It's known that multiplicative subgroups grow quickly when iterating sumsets. It's expected, for example, that $2A := A+A = \mathbb{Z}_m$ whenever $A \subseteq \mathbb{Z}_m$ is a multiplicative subgroup with $|A| > m^{0.51}$. Although this is unknown, it has been proven, for example, that $100A = \mathbb{Z}_m$ if $A \subseteq \mathbb{Z}_m$ is a multiplicative subgroup with $|A| > m^{0.3}$ (look up sum-product theorem for finite fields). Actually, that $2A = \mathbb{Z}_m$ when $|A| \ge m^{3/4}$ (and $A \le \mathbb{Z}_m^\times$) is easier to prove and might suffice for our heuristics.

The point is that, for $x_1^{a_1}+\dots+x_k^{a_k} \equiv \pmod{m}$ to have no solutions, it must be that all of the $S_i$'s have size at most a small power of $m$. But the (probabilistic) heuristics are that the order of $p_i$ (and thus the size of $|S_i|$) is randomly chosen from the multiset of orders -- where each $d \mid \phi(m)$ appears $\phi(d)$ times -- independently from the other $p_j$'s. Note $\sum_{\substack{d \mid \phi(m) \\ d < m^\alpha}} \phi(d) \le m^{1.5\alpha}$ for large enough $m$ (since $\tau(\phi(m)) \ll_\epsilon \phi(m)^{\epsilon} \ll_\epsilon m^{\epsilon}$ for any $\epsilon > 0$). So the probability that $|S_i| < m^{\alpha}$ is at most $m^{1.5\alpha}/\phi(m) \le m^{2\alpha-1}$ for large enough $m$.

Sorry, I gtg but I'll finish this later; you can now reason by basic probability and Borel-Cantelli.

  • $\begingroup$ Following your logic, for all $0<\alpha<1$ and $\varepsilon>0$ we have for $m$ large enough that $\sum_{\substack{d\mid\phi(m)\\d<m^\alpha}}\phi(d)\leq\phi(m)^\varepsilon\cdot m^\alpha$ and thus $P(|S_i|<m^\alpha)\leq m^\alpha/\phi(m)^{1-\varepsilon}$. Since $m$ is large enough, we have $\phi(m)>m^{1-\varepsilon}$, giving $P(|S_i|<m^\alpha)<m^\delta$ for $\delta:=\alpha-(1-\varepsilon)^2$. For $\varepsilon$ small enough, we have $\delta<0$. Then $P(|S_i|<m^\alpha\forall i)<m^{\delta r}$, so for $r$ large enough, the sum of this probability over all $m$ is finite, so Borel-Cantelli applies. $\endgroup$ Aug 13, 2022 at 15:04
  • $\begingroup$ @SmileyCraft Yep! For the case of $(2,2,3,3)$, we need to use heuristics twice, since we don't have a good enough sum-product theorem yet. The first heuristic/conjecture is that, for $S_p$ denoting powers of $p$, we'll have $S_2+S_2+S_3+S_3 = \mathbb{Z}_m$ if $|S_2|,|S_3| > m^{0.26}$. The second heuristic is the probabilistic one, which says that the "probability" of having $|S_2|,|S_3| \le m^{0.26}$ is around $(m^{-0.74})^2 = m^{-1.48}$ for large enough $m$ (up to factors of $m^{\epsilon}$), which is summable (over $m$). So this is a heuristic argument for why $(2,2,3,3)$ works for large $\endgroup$ Aug 14, 2022 at 5:59
  • $\begingroup$ @SmileyCraft enough $m$. But it might in fact work for all $m$. Of course we are using heuristics, but the case that $m$ is divisible by $2$ or $3$ (or in the answer, divisible by some $p_i$) should be addressed, at least heuristically. $\endgroup$ Aug 14, 2022 at 6:00

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .