Very similar to http://www.artofproblemsolving.com/Forum/viewtopic.php?p=366676

Assume that we have set of n elements, we prove find $(n+1)^{th}$ element. Let $N$ be the product of n elements there. Then have $a^{\phi (N)+1}+a^{\phi (N)} =a(mod N)$ Because all elements in that set coprime with a. Then we have QED.

Let $a^2+a-1 = p_1^{\alpha_1}p_2^{\alpha_2}....p_k^{\alpha_k}$. and let $d_1,d_2,...,d_k$ be the the order of $a$ $(mod$ $p_i$), then take the number $a^{d_1d_2...d_k}+a^{d_1d_2...d_k-1}-1$. Because $gcd(a^ 2+a-1, a)=1$ , then $a^{d_1d_2...d_k}+a^{d_1d_2...d_k-1}-1$ is congruent to $a^{d_1d_2...d_k-1}$ $(mod$ $p_i$$)$ for all $i$ and then $gcd(a^{d_1d_2...d_k}+a^{d_1d_2...d_k-1}-1,a^2+a-1) =1$. Continue this infinite process by taking the primes that divide $a^{d_1d_2...d_k}+a^{d_1d_2...d_k-1}-1$ and $a^2+a-1$ and the latter therms.

We may construct inductively; letting $N$ be the product of the first $n$ elements of the set, we can extend the set to $n+1$ elements by considering $$a^{\phi(N) + 1} + a^{\phi(N)} - 1 \equiv a \pmod N,$$which is relatively prime to all other elements as each element is relatively prime to $a$.