We will prove the statement using induction. For the base case, we choose \( n_1 = 1 \). Now, collect all the prime factors of \( a^2 + a - 1 \) into a set \( A \). Construct a set \( B \) where each element is \( \text{ord}_p(a) \) for every \( p \in A \) (note ord$_p$(a) always exists, as $a$ cannot possibly be divisible by a prime while \( a^2 + a - 1 \) is divisible by a prime). Next, collect all the prime numbers that divide at least one element of set \( B \) into a set \( C \). Using the Chinese Remainder Theorem (CRT), we construct a number \( n_2 \) such that \( n_2 \equiv 0 \pmod{q} \) for every \( q \) in \( C \). Now, observe that for every prime number \( r \) where \( r \mid a^2 + a - 1 \), it follows that \( a^{n_2 + 1} + a^{n_2} - 1 \equiv a \pmod{r} \) (because $n_2$ is a multiple of it's order). Clearly, if \( a \equiv 0 \pmod{r} \), then \( a^2 + a - 1 \equiv -1 \pmod{r} \), which is a contradiction. Thus, \( \gcd(a^{n_2+1} + a^{n_2} - 1, a^{n_1+1} + a^{n_1} - 1) = 1 \). Therefore, our base case is established. The induction step uses exactly the same method, so it is left as an exercise to the reader