Problem 1319

1. Assume for contradiction: Suppose that $\gcd(m, n) = 1$. Then, by properties of the Euler's totient function $\varphi$, we have:
$$\gcd(5^m - 1, 5^n - 1) = 5^{\gcd(m, n)} - 1 = 5^1 - 1 = 4$$

2. Claim: $\varphi(5^m - 1)$ is square-free.
- Proof: Suppose there exists an odd prime $p$ such that $p^2 \mid 5^m - 1$. Then $p \mid \varphi(5^m - 1) = 5^n - 1$. Consequently, $p \mid \gcd(5^m - 1, 5^n - 1) = 4$, which is a contradiction since $p$ is an odd prime. Hence, $\varphi(5^m - 1)$ is square-free.

3. Factorization: We can write:
$$5^m - 1 = 2^\alpha p_1 p_2 \dots p_k$$
$$5^n - 1 = 2^{\alpha - 1} (p_1 - 1)(p_2 - 1) \dots (p_k - 1)$$

4. Claim: $\alpha = 2$.
- Proof: Since $\gcd(5^m - 1, 5^n - 1) = 4$, it follows that $\alpha = 2$. Therefore, we have:
$$5^m - 1 = 4 p_1 p_2 \dots p_k$$
$$5^n - 1 = 2 (p_1 - 1)(p_2 - 1) \dots (p_k - 1)$$

5. **Parity of $n$**: If $n$ were even, then:
$$5^n - 1 \equiv (-3)^n - 1 \equiv (-1)^n - 1 \equiv 0 \pmod{4}$$
This is a contradiction, so $n$ must be odd.

6. Claim: $p_i \equiv -1 \pmod{5}$.
- Proof: Since $5^n \equiv 1 \pmod{p_i}$, by the quadratic reciprocity law, $p_i$ is a quadratic residue modulo 5. Thus, $p_i \equiv \pm 1 \pmod{5}$. If $p_i \equiv 1 \pmod{5}$, then:
$$5^n - 1 \equiv 1 - 1 \equiv 0 \pmod{5}$$
This is a contradiction. Therefore, $p_i \equiv -1 \pmod{5}$.

7. Contradiction: Given $p_i \equiv -1 \pmod{5}$, we have:
$$4 \equiv 5^m - 1 \equiv 4 p_1 p_2 \dots p_k \equiv 4^{k + 1} \pmod{5}$$
This forces $k$ to be even. However:
$$4 \equiv 5^n - 1 \equiv 2 (p_1 - 1)(p_2 - 1) \dots (p_k - 1) \equiv 2 \cdot 3^k \equiv 2 \cdot (-1)^{\frac{k}{2}} \pmod{5}$$
This is a contradiction. Therefore, our initial assumption that $\gcd(m, n) = 1$ must be false.

$\blacksquare$