3
$\begingroup$

Show that if $(b^n-1)/(b-1)$ is the power of a prime number, where $b,n>1$ are positive integers, then $n$ must be a prime number.

My solution:

If $n$ is composite, then let $n=mk$, $m,k>1$, \begin{align*} \frac{b^n-1}{b-1} &= 1+b+\cdots+b^{n-1} \\ &=(1+b+\cdots+b^{k-1} )+(b^k+b^{k+1}+\cdots+b^{2k-1}) \\ &\quad\,+\cdots+(b^{(m-1)k}+b^{(m-1)k+1}+\cdots+b^{mk-1}) \\ &=(1+b+\cdots+b^{k-1})(1+b^k+\cdots+b^{(m-1)k}) \end{align*} Which is composite and distinct, thus, for $(b^n-1)/(b-1)$ to be a power of primes, $n$ is not composite, thus it must be prime.

However, $(1+b+\cdots+b^{k-1})(1+b^k+\cdots+b^{(m-1)k})$ might be equal to $p^x \times p^y$, where $p$ is prime.

Is there any better solution?

$\endgroup$
2
  • 3
    $\begingroup$ Please use MathJax. $\endgroup$
    – Toby Mak
    Commented Mar 22, 2020 at 7:48
  • 3
    $\begingroup$ What's "a power of prime numbers"? Do you mean "a power of a prime number"? $\endgroup$
    – joriki
    Commented Mar 22, 2020 at 10:59

1 Answer 1

1
$\begingroup$

Let $(b^n-1)/(b-1)=p^x$ where $p$ is a prime and $x> 0$. If $n$ is composite, there are two cases.

  1. There exists a prime $q$ such that $n=q^m$ for some $m>1$. Note $$p^x=\frac{b^n-1}{b-1}=\frac{b^{q^m}-1}{b^{q^{m-1}}-1}\cdot \frac{b^{q^{m-1}}-1}{b-1},$$ we can assume $$\frac{b^{q^{m-1}}-1}{b-1}=p^y$$ for some $0< y< x$. Then we have \begin{align} 1+q(b-1)p^y+\sum_{i=2}^q\binom{q}{i}\left((b-1)p^y\right)^i&=\left((b-1)p^y+1\right)^q\\ &=\left(b^{q^{m-1}}\right)^q\\ &=b^{q^m}\\ &=(b-1)p^x+1, \end{align} i.e., $$q+\sum_{i=2}^q\binom{q}{i}\left((b-1)p^y\right)^{i-1}=p^{x-y}.$$ Hence, $p\mid q$. Recall that $p$ and $q$ are both primes, so $p=q$, we further have $$1+\binom{p}{2}(b-1)p^{y-1}+\sum_{i=3}^p\binom{p}{i}(b-1)^{i-1}p^{y(i-2)}=p^{x-y-1}.$$ Note the left hand side is no less than 2, so both sides are divisible by $p$, i.e., the term $\binom{p}{2}(b-1)p^{y-1}$ cannot be divisible by $p$, thus $p=2$ and $y=1$. We further have $b=p^{x-2}$, i.e., $p\mid b$ (recall that $b>1$). However, note $$p^x=\frac{b^n-1}{b-1}=1+b+\cdots+b^{n-1},$$ it is impossible that $p\mid b$.

  2. There exist two co-prime numbers $s,t>1$ such that $n=st$. In this case, we have $$p^x=\frac{b^n-1}{b-1}=\frac{b^{st}-1}{b^s-1}\cdot\frac{b^s-1}{b-1},$$ which means $(b^s-1)/(b-1)$ is divisible by $p$. Similarly, $(b^t-1)/(b-1)$ is also divisible by $p$. Since $s$ and $t$ are co-prime, there exists integers $w_s,w_t$ such that $w_ss+w_tt=1$. Without loss of generality, we assume $w_s>0$ and $w_t<0$. Then we have $$\frac{b^{w_ss}-1}{b^s-1}\cdot\frac{b^s-1}{b-1}-b\cdot\frac{b^{-w_tt}-1}{b^t-1}\cdot\frac{b^t-1}{b-1}$$ is also divisible by $p$. Note the expression above is exactly $$\left(1+b+\cdots+b^{w_ss}\right)-b\left(1+b+\cdots+b^{-w_tt}\right)=1,$$ which is impossible.

As a conclusion, $n$ must be a prime.

$\endgroup$
5
  • $\begingroup$ How did you conclude "thus $b=p=2$"? $\endgroup$
    – joriki
    Commented Mar 22, 2020 at 21:00
  • 1
    $\begingroup$ @joriki I calculated the equality wrongly. $b$ may not be 2. I have edited the answer. The conclusion is the same. Thanks for pointing out this mistake. $\endgroup$
    – xskxzr
    Commented Mar 23, 2020 at 1:04
  • $\begingroup$ OK. Now, in concluding $p\mid b$ from $b=p^{x-2}$, how did you exclude the case $x=2$? $\endgroup$
    – joriki
    Commented Mar 23, 2020 at 1:33
  • $\begingroup$ @joriki Because $b>1$ as OP mentioned in the title. $\endgroup$
    – xskxzr
    Commented Mar 23, 2020 at 1:34
  • $\begingroup$ I see. I think everything checks out then. Nice proof :-) I especially like how you used Bézout's identity. I do suspect that there should be a simpler proof, though. $\endgroup$
    – joriki
    Commented Mar 23, 2020 at 1:49

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .