Mathematical Reflections 2011, Issue 4 - Problem S204

Problem:
Find all positive integers $k$ and $n$ such that $k^n - 1$ and $n$ are divisible by precisely the
same primes.

Proposed by Tigran Hakobyan.

Solution:
We immediately see that if $k=1$, then $k^n-1$ would be divisible by every prime $p$, but since $n$ is a positive integer, $n$ is only divisible by a finite number of primes. So, we have $k > 1$. If $n = 1$, then $k-1 \geq 1$, so we obtain $k-1=1$, i.e, $k=2$. If $n=2$, then $k^2-1=(k-1)(k+1)$ and we want $$(k-1)(k+1)=2^m,$$ with $m$ a positive integer. Therefore $k=3$ and $m=1$. Now, suppose that $n > 2$. We have $$n=\prod_{i=1}^h p_i^{\alpha_i}, \qquad k=1+\prod_{i=1}^h p_i^{\beta_i},$$ with $\alpha_i, \beta_i$ positive integers and $p_i$ prime for every $1 \leq i \leq h$. Suppose $\alpha_i \neq \beta_i$ for every $1 \leq i \leq h$ and put $a=\displaystyle{\prod_{i=1}^h p_i^{\beta_i}}$. So $$\begin{array}{lll} k^n-1 & = (1+a)^n - 1 \\ & = a\left(a^{n-1}+na^{n-2}+\ldots+\dfrac{n(n-1)}{2}a+n\right) \\ & = a(ab+n) \\ & = \displaystyle{\prod_{i=1}^h p_i^{\beta_i + \min\{\alpha_i, \beta_i\}}}\left(\displaystyle{\prod_{i=1}^h p_i^{\beta_i - \min\{\alpha_i, \beta_i\}}}b+\displaystyle{\prod_{i=1}^h p_i^{\alpha_i - \min\{\alpha_i, \beta_i\}}}\right) \end{array}$$ where $b=\left(a^{n-2}+na^{n-3}+\ldots+\dfrac{n(n-1)}{2}\right)$.
It's easy to see that only one between $\displaystyle{\prod_{i=1}^h p_i^{\beta_i - \min\{\alpha_i, \beta_i\}}}$ and $\displaystyle{\prod_{i=1}^h p_i^{\alpha_i - \min\{\alpha_i, \beta_i\}}}$ is divisible by $p_i$ for every $1 \leq i \leq h$, so $$\left(\displaystyle{\prod_{i=1}^h p_i^{\beta_i - \min\{\alpha_i, \beta_i\}}}b+\displaystyle{\prod_{i=1}^h p_i^{\alpha_i - \min\{\alpha_i, \beta_i\}}}\right)$$ is not divisible by any of the $p_i$ and then is divisible by another prime $p^*$ which doesn't divide $n$, contradiction. So $\alpha_j = \beta_j$ for some $j$. Suppose that $n$ is odd. By the same argument, $$\left(\displaystyle{\prod_{i=1}^h p_i^{\beta_i - \min\{\alpha_i, \beta_i\}}}b+\displaystyle{\prod_{i=1}^h p_i^{\alpha_i - \min\{\alpha_i, \beta_i\}}}\right)$$ is not divisible by any of the $p_i$ with $i \neq j$ and for $p_j$ we have $a=p_j^{\alpha_j}a_1$ and $n=p_j^{\alpha_j}n_1$, where $a_1$ and $n_1$ are not divisible by $p_j$. Then
$$a\left(ab+n\right) = ap_j^{\alpha_j}\left(a_1b + n_1\right),$$ but since $b$ is divisible by $p_j$, $\left(a_1b + n_1\right)$ is not divisible by $p_j$ and therefore $a(ab+n)$ is not divisible by any of the prime $p_i$ for every $1 \leq i \leq h$. So $n$ is even and $a$ must be even, i.e., $a=2a_1$ with $a_1$ a positive integer and
$$\begin{array}{lll} (1+a)^n-1 & = [(1+a)^{n/2}-1][(1+a)^{n/2}+1] \\ & = [(1+a)^{n/2}-1]\left[a^{n/2} + \dfrac{n}{2} a^{n/2-1} + \ldots + \dfrac{n}{2} a + 2\right] \\ & = 2[(1+a)^{n/2}-1][2^{n/2-1}a_1^{n/2}+2^{n/2-2}a_1^{n/2-1} + \ldots + a_1 + 1] \\ & = 2c[(1+a)^{n/2}-1] \end{array}$$ where $c=[2^{n/2-1}a_1^{n/2}+2^{n/2-2}a_1^{n/2-1} + \ldots + a_1 + 1]$.
Since $c$ is not divisible by $a_1$, any prime which divides $a_1$ (and $a$) doesn't divide $c$ and then $c$ is not divisibile by any prime which divides $n$ and thus is divisible by another prime which doesn't divide $n$. This contradiction shows that the only positive integers which satisfy the required conditions are $n=1, k=2$ and $n=2, k=3$.