Problem 1509

1. Define the functions $f(n)$ and $g(n)$ as follows:
$$f(n) = \underbrace{2^{2^{\cdots^2}}}_{n \text{ times}}, \quad g(n) = f(n) - f(n-1)$$
Here, $f(n)$ represents the tower of exponents with $n$ layers of 2's.

2. Observe that:
$$g(n) = f(n-1) \left( 2^{g(n-1)} - 1 \right)$$
This follows from the fact that $f(n) = 2^{f(n-1)}$.

3. Let $n$ be an odd number and let $\text{ord}_2(n)$ be the minimal positive integer $k$ such that $n \mid 2^k - 1$. This is the order of 2 modulo $n$.

4. Define $x(n)$ as the maximal odd divisor of $n$ and $c(n) = x(\text{ord}_2(x(n)))$.

5. We need to show that $n \mid f(n) - f(n-1)$. We will use induction on $n$.

6. Base case: For $n = 2$, we have:
$$f(2) = 2^2 = 4, \quad f(1) = 2$$
Thus,
$$f(2) - f(1) = 4 - 2 = 2$$
Clearly, $2 \mid 2$.

7. Inductive step: Assume that for some $k \geq 2$, $k \mid f(k) - f(k-1)$. We need to show that $k+1 \mid f(k+1) - f(k)$.

8. By the induction hypothesis, $k \mid f(k) - f(k-1)$. We need to show that $k+1 \mid f(k+1) - f(k)$.

9. Consider the expression:
$$f(k+1) = 2^{f(k)}$$
and
$$f(k) = 2^{f(k-1)}$$
Therefore,
$$f(k+1) - f(k) = 2^{f(k)} - 2^{f(k-1)}$$

10. Since $k \mid f(k) - f(k-1)$, we have $f(k) \equiv f(k-1) \pmod{k}$. Thus,
$$2^{f(k)} \equiv 2^{f(k-1)} \pmod{k}$$
This implies that:
$$2^{f(k)} - 2^{f(k-1)} \equiv 0 \pmod{k}$$

11. Now, we need to show that $k+1 \mid 2^{f(k)} - 2^{f(k-1)}$. Since $k+1$ is coprime to $k$, we can use the Chinese Remainder Theorem to conclude that $k+1 \mid 2^{f(k)} - 2^{f(k-1)}$.

12. Therefore, by induction, $n \mid f(n) - f(n-1)$ for all $n \geq 2$.

$\blacksquare$