Size of smallest multiple $\sum \epsilon_i p^i$ of $n$ with digits $\epsilon_i\in \{0,1\}$ for $p$ a prime

Question

Any natural number $n$ coprime with a prime number $p$ is a divisor of $M=1+p+p^2+\dots+P^{N-1}$ where $N\leq \varphi((p-1)n)$ is the order of $p$ in $\left(\mathbb Z/((p-1)n)\mathbb Z\right)^*$.

The integer $M$ is minimal with this property and is of course in general exponentially larger than $n$.

(Added correction: The minimal integer M is in fact given by $N=\varphi(n)$ for $n$ coprime to $p-1$. Thanks to Seva for this remark.)

Can this exponential bound be improved to a polynomial one when allowing digits in $\{0,1\}$? Otherwise stated, given a prime number $p$, does there exist a constant $\alpha=\alpha(p)$ such that every natural integer $n$ has a non-zero multiple $M=dn$ with $M\leq n^\alpha$ a sum of distinct powers of $p$?

(The result is of course trivially true for $p=2$.)

There are of course many related questions:

If yes, what is asymptotically the best constant $\alpha$ (i.e. we want $M\leq n^{\alpha(1+\epsilon)}$ for all $\epsilon>0$ and for all but a finite number of $n$)?

How does $\alpha$ grow with $p$? (A trivial lower bound comes from a counting argument.)

Etc.

Added after a comment of Douglas Zare: The question makes of course perfectly sense for non-prime $p\geq 2$.

Answer 1

While $M=n^{O_p(1)}$ can be tricky (or out of reach), the following argument shows that $M\le p^{(2+o(1))\sqrt{dn}}$ with $d=\gcd(p-1,n)$; thus, $M<\exp(O(\sqrt n))$ in the regime where $p$ is fixed and $n$ grows.

Recall that the critical number of a finite abelian group $G$ is defined to be the smallest positive integer $k=k(G)$ such that for any $k$-element subset $A\subset G\setminus\{0\}$, every element of $G$ is representable as a non-empty sum of pairwise distinct elements of $A$. It is known that if $G$ is cyclic, then its critical number is at most $(2+o(1))\sqrt{|G|}$; see, for instance the paper by Hamidoune, Llado, and Serra "On Complete Subsets of the Cyclic Group".

Let now $k$ being the critical number of the group ${\mathbb Z}/dn{\mathbb Z}$, so that $k\le(2+o(1))\sqrt{dn}$. If the order of $p$ in this group does not exceed $k-1$, then we have $p^s\equiv 1\pmod{dn}$ with some $s\le k-1$, implying $n\mid 1+p+\dotsb+p^{s-1}$; thus, we can set $M:=1+p+\dotsb+p^{s-1}$. Otherwise, consider the set $A:=\{1,p,p^2,\ldots,p^{k-1}\}$. By the definition of a critical number, one can select several elements from this set so that their sum is divisible by $dn$, and we define $M$ to be the sum of these numbers.

---

One further observation is that if $p\equiv 1\pmod n$, then in order for a sum of powers of $p$ to be divisible by $n$, one needs to have at least $n$ such powers; hence, $M>p^{n-1}$ in this case. This does not, of course, show that $M<n^{O(1)}$ fails to hold, as the assumption $p\equiv 1\pmod n$ is incompatible with the regime where $p$ is fixed and $n$ grows.