$F_n,$ but not Fibonacci

We will first prove these two lemmas:

Lemma 1: $\gcd(a^m - 1, a^n - 1) = a^{\gcd(m, n)} - 1.$

Proof of Lemma 1: Let $d = \gcd(a^n - 1, a^m - 1).$ WLOG we can assume that $m \geq n.$ Thus, we can write $m = nq_1 + r_1,$ where $q_1, r_1$ are integers with $q_1 > 0$ and $0 \leq r_1 < n.$ By the Euclidean Algorithm,

$d = \gcd(a^m - 1, a^n - 1) = \gcd((a^m - 1) - (a^{nq_1}- 1), a^n - 1) = \gcd(a^n(a^{m - nq_1} - 1), a^n - 1) = \gcd(a^{r_1} - 1, a^n - 1).$

Since $n > r_1,$ we can write $n = q_2r_1 + r_2,$ so that by applying the Euclidean Algorithm again as shown above, we get $d = \gcd(a^{r_2} - 1, a^{r_1} - 1).$ Eventually, after repeating this process some number of times, we end up with $r_{k - 1} = q_{k + 1}r_k$ so $d = a^{r_k} - 1.$ But note that $r_k$ is precisely the greatest common divisor of $m$ and $n,$ because the process that we used to reduce the exponents is the Euclidean Algorithm applied to $m, n.$ Thus, $r_k = \gcd(m, n),$ and $d = a^{\gcd(m, n)} - 1. \, \blacksquare$

Lemma 2: If $m \neq n,$ then $\gcd(F_m, F_n) = 1.$

Proof of Lemma 2: For this proof, we utilize the identity

$F_n = F_0 F_1 \cdots F_{n - 1} + 2.$

This can be proven with induction: for $n = 1,$ $F_1 = 2^2 + 1 = 5 = 3 + 2 = F_0 + 2,$ and if it's true for $n = k,$ then

$F_{k + 1} = 2^{2^{k + 1}} + 1 = \left ( 2^{2^k} \right )^2 - 1 + 2 = \left (2^{2^k} - 1 \right) \left (2^{2^k} + 1 \right) + 2 = F_n(F_n - 2) + 2 = F_0F_1 \cdots F_k + 2,$

so it's also true for $n = k + 1.$

Again, WLOG we assume that $m > n.$ We have

$\gcd(F_m, F_n) = \gcd(F_0F_1 \cdots F_{n - 1}F_nF_{n + 1} \cdots F_{m - 1} + 2, F_n) = \gcd(2, F_n).$

However, $F_n$ is always odd, so $\gcd(2, F_n) = 1,$ and we are done. $\blacksquare$

The problem is a direct application of these two lemmas. WLOG let $a > b.$ Applying Lemmas 1 and 2, we have

$\gcd(2018^{F_a} - 1, 2018^{F_b} - 1) = 2018^{\gcd(F_a, F_b)} - 1 = 2018^1 - 1 = \boxed{2017}.$

In general, $\gcd(n^{F_a} - 1, n^{F_b} - 1) = n - 1$ for all positive integers $n$ greater than 1.