Question

Let $f(n) = n^2 + 100$. Compute the remainder when $\underbrace{f(f(\cdots f(f(1))\cdots))}_{2025 \text{ } f's}$ is divided by $10^4$.

Answer 1

3101

Answer 2

Let the given function be $f(n) = n^2 + 100$. We need to compute the remainder when $\underbrace{f(f(\cdots f(f(1))\cdots))}_{2025 \text{ } f's}$ is divided by $10^4$. Let $x_0 = 1$. Let $x_{k+1} = f(x_k) = x_k^2 + 100$. We need to find $x_{2025} \pmod{10^4}$.

Let's compute the first few terms modulo $10^4$: $x_0 = 1$ $x_1 = f(x_0) = f(1) = 1^2 + 100 = 101$ $x_2 = f(x_1) = f(101) = 101^2 + 100 = (100+1)^2 + 100 = (100^2 + 2 \cdot 100 \cdot 1 + 1^2) + 100$ $x_2 = 10000 + 200 + 1 + 100 = 10301$ $x_2 \equiv 301 \pmod{10000}$

$x_3 = f(x_2) = x_2^2 + 100$ $x_3 \equiv 301^2 + 100 \pmod{10000}$ $301^2 = (300+1)^2 = 300^2 + 2 \cdot 300 \cdot 1 + 1^2 = 90000 + 600 + 1 = 90601$ $x_3 \equiv 90601 + 100 \pmod{10000}$ $x_3 \equiv 90701 \pmod{10000}$ $x_3 \equiv 701 \pmod{10000}$

$x_4 = f(x_3) = x_3^2 + 100$ $x_4 \equiv 701^2 + 100 \pmod{10000}$ $701^2 = (700+1)^2 = 700^2 + 2 \cdot 700 \cdot 1 + 1^2 = 490000 + 1400 + 1 = 491401$ $x_4 \equiv 491401 + 100 \pmod{10000}$ $x_4 \equiv 491501 \pmod{10000}$ $x_4 \equiv 1501 \pmod{10000}$

Let's observe the pattern of $x_k \pmod{10000}$ for $k \ge 1$: $x_1 \equiv 101 \pmod{10000}$ $x_2 \equiv 301 \pmod{10000}$ $x_3 \equiv 701 \pmod{10000}$ $x_4 \equiv 1501 \pmod{10000}$

It appears that $x_k \equiv 100a_k + 1 \pmod{10000}$ where $a_k$ follows a pattern. $a_1 = 1$ $a_2 = 3$ $a_3 = 7$ $a_4 = 15$ This suggests $a_k = 2^k - 1$.

Let's prove this by induction. Base case: For $k=1$, $a_1 = 2^1 - 1 = 1$. This holds for $x_1 = 101$. Inductive step: Assume $x_k \equiv 100(2^k-1) + 1 \pmod{10000}$ for some $k \ge 1$. Then $x_{k+1} = x_k^2 + 100$. Substitute the assumed form of $x_k$: $x_{k+1} \equiv (100(2^k-1) + 1)^2 + 100 \pmod{10000}$ Using $(A+B)^2 = A^2 + 2AB + B^2$: $x_{k+1} \equiv (100(2^k-1))^2 + 2 \cdot 100(2^k-1) \cdot 1 + 1^2 + 100 \pmod{10000}$ $x_{k+1} \equiv 10000(2^k-1)^2 + 200(2^k-1) + 1 + 100 \pmod{10000}$ Since $10000(2^k-1)^2$ is a multiple of $10000$, it becomes $0 \pmod{10000}$. $x_{k+1} \equiv 200(2^k-1) + 101 \pmod{10000}$ $x_{k+1} \equiv 200 \cdot 2^k - 200 + 101 \pmod{10000}$ $x_{k+1} \equiv 100 \cdot 2 \cdot 2^k - 99 \pmod{10000}$ $x_{k+1} \equiv 100 \cdot 2^{k+1} - 99 \pmod{10000}$ $x_{k+1} \equiv 100(2^{k+1}-1) + 1 \pmod{10000}$ This completes the induction. So, $x_k \equiv 100(2^k-1) + 1 \pmod{10000}$ for $k \ge 1$.

We need to compute $x_{2025} \pmod{10000}$. Using the formula for $k=2025$: $x_{2025} \equiv 100(2^{2025}-1) + 1 \pmod{10000}$ $x_{2025} \equiv 100 \cdot 2^{2025} - 100 + 1 \pmod{10000}$ $x_{2025} \equiv 100 \cdot 2^{2025} - 99 \pmod{10000}$

To evaluate this, we need to find $2^{2025} \pmod{100}$. We can use the Chinese Remainder Theorem since $100 = 4 \times 25$.

1. Modulo 4: Since $2025 \ge 2$, $2^{2025}$ is divisible by $4$. So, $2^{2025} \equiv 0 \pmod 4$.

2. Modulo 25: We use Euler's totient theorem. $\phi(25) = 25(1 - 1/5) = 20$. So, $2^{20} \equiv 1 \pmod{25}$. Now, we find the exponent $2025 \pmod{20}$: $2025 = 20 \times 101 + 5$. So, $2^{2025} = (2^{20})^{101} \cdot 2^5 \equiv 1^{101} \cdot 2^5 \pmod{25}$ $2^5 = 32$. $2^{2025} \equiv 32 \pmod{25}$ $2^{2025} \equiv 7 \pmod{25}$.

Now we have a system of congruences: Let $N = 2^{2025}$. $N \equiv 0 \pmod 4$ $N \equiv 7 \pmod{25}$

From the second congruence, $N = 25k + 7$ for some integer $k$. Substitute this into the first congruence: $25k + 7 \equiv 0 \pmod 4$ $k + 3 \equiv 0 \pmod 4$ (since $25 \equiv 1 \pmod 4$ and $7 \equiv 3 \pmod 4$) $k \equiv -3 \pmod 4$ $k \equiv 1 \pmod 4$ So $k = 4m + 1$ for some integer $m$. Substitute $k$ back into the expression for $N$: $N = 25(4m+1) + 7 = 100m + 25 + 7 = 100m + 32$. Therefore, $2^{2025} \equiv 32 \pmod{100}$.

Finally, substitute this result back into the expression for $x_{2025}$: $x_{2025} \equiv 100 \cdot 2^{2025} - 99 \pmod{10000}$ Let $2^{2025} = 100m + 32$. $x_{2025} \equiv 100(100m + 32) - 99 \pmod{10000}$ $x_{2025} \equiv 10000m + 3200 - 99 \pmod{10000}$ $x_{2025} \equiv 3200 - 99 \pmod{10000}$ $x_{2025} \equiv 3101 \pmod{10000}$

The remainder is 3101.