Return to 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 with $N=\varphi(n)$. 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$.

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

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

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

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 with $N=\varphi(n)$. 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$.

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

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 but a finite number of $n$)?

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

Etc.

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

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