SAUDI ARABIAN MATHEMATICAL COMPETITIONS

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=\mathrm{lcm}(p^r-1,p^p-1)$, then $$(p^r-1)(p^p-1)=xy.$$ 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^{pr}-1}{y}$. But $p^r-1\mid p^{pr}-1$ and $p^p-1\mid p^{pr}-1$, so $y\mid p^{pr}-1$ leads to $F(r)$ being a positive integer.

2. We can see that $$\gcd (p^{rp}-1,p^{sp}-1)=p^{\gcd (rp,sp)}-1=p^p-1.$$ Let $p^{rp}-1=(p^p-1)r_1$, $p^{sp}-1=(p^p-1)s_1$ with $\gcd (r_1,s_1)=1$, then $$\begin{array}{rl}\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{array}$$

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^{rp}-1}{(p^r-1)f(p)}$, so $q\mid p^{rp}-1$. These imply that $$q\mid \gcd (p^{q-1}-1,p^{rp}-1)=p^{\gcd (q-1,rp)}-1$$ Since $r,p$ are two primes, $d=\gcd (q-1,rp)\in \{1,r,p,rp\}$. We have to consider 4 following cases:

1. If $d=p$ or $d=rp$, we get $p\mid q-1$ and () follows. 2. If $d=1$, we have $q\mid p-1$ or $p\equiv 1(\mathrm{mod}q)$. We also have $$0\equiv \frac{p^{rp}-1}{p^p-1}=p^{p(r-1)}+p^{p(r-2)}+\cdots +p^p+1\equiv p\equiv 1(\mathrm{mod}q),$$ contradiction. 3. If $d=r$, we have $q\mid p^r-1$ or $p^r\equiv 1(\mathrm{mod}q)$. We also have $$0\equiv \frac{p^{rp}-1}{p^r-1}=p^{r(p-1)}+p^{r(p-2)}+\cdots +p^r+1\equiv r(\mathrm{mod}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(\mathrm{mod}{p}^2)$. Note that $$F(r)(p^p-1)(p^r-1)=(p^{rp}-1)(p-1)=p^{rp+1}-p^{rp}-(p-1)\equiv -(p-1)(\mathrm{mod}{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(\mathrm{mod}{p}^2).$$ These imply that $$1\equiv -(p-1)(\mathrm{mod}{p}^2)\iff p\equiv 0(\mathrm{mod}{p}^2),$$ which is a contradiction.

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