Does $x_1^{a_1}+\dots+x_k^{a_k}\equiv0$ always have no solution modulo some $m$.

Question

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.

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.