Problem 1413

Notice that with positive integers $a, m, n$ and $a > 1$, we have
$$\gcd(a^m - 1, a^n - 1) = a^{\gcd(m, n)} - 1.$$
Let $f(r) = \frac{p^r - 1}{p - 1}$ with $p$ a prime and $r$ a positive integer.

1.
Let $x = \gcd(p^r - 1, p^p - 1)$ and $y = \operatorname{lcm}(p^r - 1, p^p - 1)$, then
$$(p^r - 1)(p^p - 1) = x y.$$
From the above lemma, we get $x = p^{\gcd(r, p)} - 1 = p - 1$. Hence $(p^r - 1)(p^p - 1) = (p - 1) y$, which implies that $F(r) = \frac{p^{p r} - 1}{y}$. But $p^r - 1 \mid p^{p r} - 1$ and $p^p - 1 \mid p^{p r} - 1$, so $y \mid p^{p r} - 1$ leads to $F(r)$ being a positive integer.

2.
We can see that
$$\gcd(p^{r p} - 1, p^{s p} - 1) = p^{\gcd(r p, s p)} - 1 = p^p - 1.$$
Let $p^{r p} - 1 = (p^p - 1) r_1$, $p^{s p} - 1 = (p^p - 1) s_1$ with $\gcd(r_1, s_1) = 1$, then
$$\begin{aligned} \gcd(F(r), F(s)) &= \gcd\left(\frac{(p^p - 1) r_1 (p - 1)}{(p^r - 1)(p^p - 1)}, \frac{(p^p - 1) s_1 (p - 1)}{(p^s - 1)(p^p - 1)}\right) \\ &= \gcd\left(\frac{r_1}{f(r)}, \frac{s_1}{f(s)}\right) = 1 \end{aligned}$$

3.
At first, we will show that with any prime divisor $q$ of $F(r)$, we always have $p \mid q-1$. (*)
Indeed, from Fermat's theorem, $q \mid p^{q-1} - 1$ and because $q \mid \frac{p^{r p} - 1}{(p^r - 1) f(p)}$, so $q \mid p^{r p} - 1$.
These imply that
$$q \mid \gcd(p^{q-1} - 1, p^{r p} - 1) = p^{\gcd(q-1, r p)} - 1$$
Since $r, p$ are two primes, $d = \gcd(q-1, r p) \in \{1, r, p, r p\}$. We have to consider 4 following cases:

1. If $d = p$ or $d = r p$, we get $p \mid q-1$ and (*) follows.
2. If $d = 1$, we have $q \mid p - 1$ or $p \equiv 1 \pmod{q}$. We also have
$$0 \equiv \frac{p^{r p} - 1}{p^p - 1} = p^{p(r-1)} + p^{p(r-2)} + \cdots + p^p + 1 \equiv p \equiv 1 \pmod{q},$$
contradiction.
3. If $d = r$, we have $q \mid p^r - 1$ or $p^r \equiv 1 \pmod{q}$. We also have
$$0 \equiv \frac{p^{r p} - 1}{p^r - 1} = p^{r(p-1)} + p^{r(p-2)} + \cdots + p^r + 1 \equiv r \pmod{q},$$
contradiction.

Hence (*) is true. Finally, assume that for all prime $q \mid F(r)$, we always have $p^2 \mid q-1$.
Because all divisors of $F(r)$ are congruent to $1$ modulo $p^2$, then $F(r) \equiv 1 \pmod{p^2}$.
Note that
$$F(r)(p^p - 1)(p^r - 1) = (p^{r p} - 1)(p - 1) = p^{r p + 1} - p^{r p} - (p - 1) \equiv -(p - 1) \pmod{p^2}$$
and
$$F(r)(p^p - 1)(p^r - 1) = F(r)(p^{p + r} - p^r - p^p + 1) \equiv F(r) \equiv 1 \pmod{p^2}.$$
These imply that
$$1 \equiv -(p - 1) \pmod{p^2} \Leftrightarrow p \equiv 0 \pmod{p^2},$$
which is a contradiction.

Therefore, there exists a prime satisfying all the given conditions. $\square$