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

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.

• $x \geq 2$ does lose some generality. But you can just cover the case $x = 1$ separately, with just $m=k+1$. Commented May 7, 2022 at 23:46
• Perhaps I abused the phrase wlog. I just wanted to omit the trivial case really :P Commented May 7, 2022 at 23:56
• 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. Commented May 23, 2022 at 22:30

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.

• 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. Commented Aug 13, 2022 at 15:04
• @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 Commented Aug 14, 2022 at 5:59
• @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. Commented Aug 14, 2022 at 6:00