How to find GCD between these two equations? I've been trying for a couple of hours to find a way to prove the next claim:
$$\gcd(n-1,a) = \gcd(\frac{(n^a-1)}{n-1},n-1)$$
I have already proven that 
$$\frac{(n^a-1)}{n-1}$$ is always divisible by $(a-1)$.
which means I can set define 
$$\frac{(n^a-1)}{n-1}=\frac{c(n-1)}{n-1}=c$$
then I get :
   $$  \gcd(n-1,a)=\gcd(c,n-1)$$
but that's it, I'm stuck. 

You can expand $n^a - 1$ as a difference of $a$th powers:
\begin{equation*}
 n^a - 1 = (n - 1)(n^{a - 1} + n^{a - 2} + \dotsb + 1)
\end{equation*}
so
\begin{equation*}
 \frac{n^a - 1}{n - 1} = n^{a - 1} + n^{a - 2} + \dotsb + 1
\end{equation*}
But since
\begin{align*}
 n^{a - 1} + n^{a - 2} + \dotsb + 1 &\equiv
 \underbrace{1^{a - 1} + 1^{a - 2} + \dotsb + 1}_{\text{$a$ times}} \pmod{n - 1} \\
 &\equiv a \pmod{n - 1}
\end{align*}
we can use the property $\gcd(a, b) = \gcd(a, na + b)$
to infer that
\begin{equation*}
 \gcd(n - 1, n^{a - 1} + n^{a - 2} + \dotsb + 1) = \gcd(n - 1, a)
\end{equation*}
