Problem 2151

Let us denote by $a|b$ when a positive integer $a$ divides $b$. We write $p^c \nmid n$ when a positive integer $n$ is a multiple of $p^c$, but not of $p^{c+1}$ for a prime $p$.

Lemma 1. For a given prime $q$ and a positive integer $a$ such that $(a, q) = 1$, let $s$ be the smallest positive integer $x$ satisfying $q|a^s - 1$. Any positive integer $y$ such that $q|a^y - 1$ must be a multiple of $s$.
Proof. Put $y = qs + r_0$, where $q, r_0$ are integers and $0 \le r_0 < s$. Noting $q|a^y - 1 = (a^s - 1)(a^{y-s} + a^{y-2s} + \dots + a^{r_0}) + a^{r_0} - 1$ leads us to $q|a^{r_0} - 1$. By the minimality of $s$, we get $r_0 = 0$. $\square$

1. The case of $p = 2$
It is immediate to note that all $n_i$s are odd and greater than or equal to $3$. Let $q (\ge 3)$ be the smallest prime dividing one of $n_1, n_2, \dots, n_k$. Without loss of generality, we assume $q|n_2$. Let $s \ge 2$ be the smallest positive integer $x$ satisfying $q|2^r - 1$. Then by Fermat's little theorem and Lemma 1, we get $s|q - 1$. Thus $s < q$. We realize that $s$ has a smaller prime factor than $q$, so it contradicts $q|2^{n_1} - 1$, which implies $s|n_1$. We conclude that there does not exist $(n_1, n_2, \dots, n_k)$ fulfilling conditions, hence $2$ is not a nice prime.

2. The case of prime $p \ge 3$
(1) In the case $k = 1$: we prove that there does not exist a positive integer $n$ such that $n|p^n - 1$ and $\left(\frac{p^n-1}{n}, n\right) = 1$.
First, under the condition $n|p^n - 1$, we show the smallest prime factor $q_1$ of $n$ must divide $p-1$. Let $n = q_1^{e_1} \cdots q_r^{e_r}$, $q_1 < \cdots < q_r$. $n|p^n - 1$ implies $q_1|p^n - 1$. Let $s$ be the smallest positive integer $x$ such that $q_1|p^x - 1$. Then it is obvious that $s \le q_1 - 1$ and $s|n$. If $s > 1$, $s$ is a product of primes smaller than $q_1$, it violates that $n$ cannot have smaller prime factors than $q_1$. We obtain $s = 1$ so $q_1|p - 1$.
Now let $n = q_1^{e_1} n_0$. In the expression $p^n - 1 = p^{q_1^{e_1} n_0} - 1 = (p^{n_0} - 1) \prod_{j=0}^{e_1-1} \frac{p^{q_1^{j} n_0} - 1}{p^{q_1^{j-1} n_0} - 1}$. We easily see the number of prime $q_1$ in $p^n - 1$ is at least $e_1 + 1$. So we get $q_1|\left(\frac{p^n-1}{n}, n\right)$ reducing to contradiction. In sum, for any given prime $p$, there does not exist a positive integer $n$ satisfying all conditions when $k = 1$.

(2) In the case $k \ge 2$: we are always able to find sequences of positive integers $(n_1, n_2, \dots, n_k)$ for infinitely many $k$. This proves that any odd primes are nice. There are various ways of taking the sequences and the proposed way below is one of them.

Lemma 2. For a positive integer $c$ and a prime $q$, $q^c|p-1$ implies $q^{c+d}|p^{q^d} - 1$. Moreover,
- When $q$ is odd or $(q = 2, c \ge 2)$: the smallest positive integer $x$ such that $q^{c+d}|p^x - 1$ is $q^d$ and $q^{c+d}||p^{q^d} - 1$ holds.
- When $(q = 2, c = 1)$: Let $c'$ be the smallest positive integer such that $2^{c'}||p^2 - 1$. Then the smallest positive integer $x$ satisfying $2^{c'-d}||p^x - 1$ is $2^{d+1}$ and $2^{c'+d}||p^{2d+1}-1$ holds.

Proof. Let us show only the first case. When $d=0$, it is true by definition. Let us assume the statement is true when $d=d_0$ and try to show when $d=d_0+1$. We need to find the smallest positive integer $x$ such that $q^{c+d_0+1}||p^x-1$. Since $q^{c+d_0}||p^x-1$ also holds, by the assumption, $x$ is a multiple of $q^{d_0}$ and we set $x=q^{d_0}u$. From the equation $p^x-1 = p^{q^{d_0}u}-1 = (p^{q^{d_0}}-1)(p^{(u-1)q^{d_0}}+p^{(u-2)q^{d_0}}+\cdots+1)$, $p^{q^{d_0}}-1$ is already a multiple of $q^{c+d_0}$, so it is enough to have $p^{(u-1)q^{d_0}}+p^{(u-2)q^{d_0}}+\cdots+1$ a multiple of $q$. $p^{(u-1)q^{d_0}}+p^{(u-2)q^{d_0}}+\cdots+1\equiv 1+\cdots+1\equiv u\pmod q$ implies $q\nmid u$ and conversely, we easily check $p^x-1$ is really a multiple of $q^{c+d_0+1}$ when $q$ divides $u$. Thus $x=q^{d_0}u$ is a multiple of $q^{d_0+1}$.
On the other hand, $\frac{p^{q^{d_0}}-1}{p^{q^{d_0}-1}} = p^{(q-1)q^{d_0}} + p^{(q-2)q^{d_0}} + \cdots + 1$ is only a multiple of $q$ not of $q^2$, whose proof is presented below. In conclusion, we obtain $q^{c+d}||p^{q^d}-1$ by induction.
The reason for $q||p^{(q-1)q^{d_0}} + p^{(q-2)q^{d_0}} + \cdots + 1$: Let $v$ be a positive integer such that $p^{q^{d_0}} = 1+qv$. Then, $p^{(q-1)q^{d_0}} + p^{(q-2)q^{d_0}} + \cdots + 1 = (1+qv)^{q-1} + (1+qv)^{q-2} + \cdots + (1+qv) + 1 \equiv 1 + (q-1)qv + 1 + (q-2)qv + \cdots + (1+qv) + 1 = q + \frac{(q-1)q^2}{2}v \equiv q \pmod{q^2}$.
In the case $(q=2, c=1)$, we are not able to guarantee the term $\frac{(q-1)q^2}{2}v$ in the almost last equation is a multiple of $q^2$ so we separate the case. $\square$

Now we define $S = \{q|q$ a prime dividing $p-1\}$ and let $q \in S$. Take $n_1 = p-1$ and let $c_{q,1}$ be an integer such that $q^{c_{q,1}}||p-1$ for $q \in S$. Similarly, we define $c_{q,2}$ as an integer satisfying $q^{c_{q,2}}||p^{n_1}-1 = p^{n_1-1}-1$. Inductively for $q \in S, i \ge 1$, let $c_{q,i+1}$ be an integer such that $q^{c_{q,i+1}}||p^{n_i}-1$ and $n_{i+1} := \prod_{q \in S} q^{c_{q,i+1}}$.
We define $c_{q,i}$ and $n_i$ in this way accordingly as $i$ gets increased one by one, then we notice that $c_{q,i}$ also gets large as $i$ does so. Fix $q_0 \in S$ and put $c := c_{q_0,1}$. (When $q_0 = 2, c_{q_0,1} = 1$, let $c = c' - 1$, where $c'$ is in Lemma 2.(ii).)
Since there exists an integer $i$ such that $q_0^{c_{q_0,i}} > p-1$, we call such $i$ $i_0$. Moreover, there exists a positive integer $k_0$ such that $\frac{p^{k_0}-1}{(p-1)q_0^{k_0}} \ge \frac{p+1}{2}$, which is justified by that the left hand side is a function divergent when $k_0$ goes to infinity. Now let $k$ be any integer greater than $1 + \max\{i_0, k_0, 3\}$. Except the case $q_0 = 2, c_{q_0,1} = 1$, we can, in fact, define $k$ to be any integer greater than $\max\{i_0, k_0, 3\}$. We apply the above definition of $c_{q,i+1}$ and $n_{i+1}$ till $i < k-2$ and let $n_{k-1} := q_0^{c_{q_0,k-1}}$. It is easy to observe $n_{k-1} \ge p-1 \ge \frac{p-1}{2}$.
From our choices of sequences $\{n_i\}$, it is clear to verify the following for $1 \le i < k-1$
$$-1, n_1 = p-1 \ge \frac{p+1}{2}, n_{i+1} = p-1 \ge \frac{p+1}{2}$$
$$-2, n_{i+1} | p^{n_i} - 1, \left( \frac{p^{n_i-1}}{n_{i-1}}, n_{i+1} \right) = 1$$
The first one comes from $c_{q,i+1} > c_{q,i} \ge 1$. From Lemma 2, we even know $c_{q,i+1} = c_{q,i} + c_{q,i}$ holds when $q$ is odd or $c_{q,i} \ge 2$.
Finally, let $n_k := \frac{p^{n_k} - 1}{q_0^{c_{q_0,k-1}} \prod_{q \in S} q^{c_{q,q}}} = \frac{p^{n_k} - 1}{q_0^{c_{q_0,k-1}}(p-1)}$, then $(n_k, q_0) = 1$ follows from Lemma 2, hence it satisfies the second condition $(n_k, \frac{p^{n_k} - 1}{n_k}) = 1$ for $n_k$.
We also obtain the first condition $n_k \ge \frac{p+1}{2}$ from $\frac{p^{n_k} - 1}{(p-1)q_0^{c_{q_0,k-1}}} \ge \frac{p+1}{2}$. Noting $(p-1, \frac{p^{n_k}-1}{p-1}) = (p-1, n_k)$ for this $n_k$ and $(q, n_k) = 1$ for $q \in S$, we establish $(p-1, n_k) = 1$. $\square$