# Partition of a prime $p$ into primes raised to a power to be dvisible by $p$

Find all the partitions of prime $p$ in primes less than $p$. Raise each term in each partition by some power $k > 1$ to see if the sum of these terms will be divisible by $p$. Of course, $k$ can differ for each partition. For example, for $5$, $2^3 + 3^3 = 35 = 5 \times 7$ and for $11$, $4 \times 2^4 + 3^4 = 209 = 11 \times 19$. Do you think all partitions will eventually have some least power $k$? Will it be less than $p$ itself?

There always exists such a least power $k > 1$, and it will certainly never be greater than $p$, because $p$ itself is a valid power:

By Fermat's little theorem, $a^p \equiv a \bmod p$. So if $a_1 + \ldots + a_n$ is divisible by $p$, then so is ${a_1}^p + \ldots + {a_n}^p$.

As McFry has already answered, the first question is answered by Fermat's little theorem: Since $a^p+b^p+\cdots+z^p\equiv a+b+\cdots+z$, there will always be a least power satisfying the OP's condition, and that least power will be no greater than $p$.

As for the second question, $p=7=2+2+3$ is an example where the least power is $p$. That is, $7$ does not divide any of the numbers $4+4+9=17$, $8+8+27=43$, $16+16+81=113$, $32+32+243=309$, or $64+64+729=857$.

It could be of interest to see how often $p$ is the least power for one of its partitions. To summarize the small examples (and someone should doublecheck this), the smallest powers for prime-only partitions of $7$ and $11$ are

\begin{align} 2^3+5^3&=7\cdot19\\ 2^7+2^7+3^7&=7\cdot349\\ 2^6+2^6+7^6&=11\cdot10707\\ 3^6+3^6+5^6&=11\cdot1553\\ 2^{11}+2^{11}+2^{11}+5^{11}&=11\cdot4439479\\ 2^{11}+3^{11}+3^{11}+3^{11}&=11\cdot48499\\ 2^4+2^2+2^4+2^4+3^4&=11\cdot19 \end{align}

(so $2$ out of $5$ prime-only partitions of $11$ have least power $11$).

• For those who enjoy computer experimentation, take some p and do a distribution of the required powers k for all the partitions. How many k's will be relatively small compared to p? From the factoring one notices many semiprimes. Is there something unusual going on here? Again, yet another task for a computer fan! – J. M. Bergot Sep 18 '16 at 20:08