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$).

  • $\begingroup$ 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! $\endgroup$ – J. M. Bergot Sep 18 '16 at 20:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.