<s>[INST] How can I find $\gcd(n^a-1,m^a-1)$? From Prove that $\gcd(a^n - 1, a^m - 1) = a^{\gcd(n, m)} - 1$ , we have $$\gcd(a^n-1,a^m-1)=a^{\gcd(n,m)}-1$$
for every positive integers $a,n,m$.
I reversed $a$ with $n,m$, and I had this question: 

Find $\gcd(n^a-1,m^a-1)$ for every positive integers $a,n,m$

My attempt is to find the greatest common divisor of $n^p-1$ and $m^p-1$ for every prime $p$ such that $p|a$, but I couldn't get any further. 
How can I find the general formula of $\gcd(n^a-1,m^a-1)$ ?
(sorry for my grammar mistake, English is my second language)
 [/INST] Welcome. If n and m are as following forms:
$n=k b+1$ ⇒ $n≡1\mod b$⇒ $n^a≡1\mod b$
$m=t b+1$ ⇒ $m≡1 \mod b$⇒$m^a≡1\mod b$
Then the common divisor will be:
$gcd(n^a-1, m^a-1)=b$
In other words if $n-1$ and $m-1$ have a common divisor like b then $n^a-1$ and $m^a-1$ have a common divisor like b. This can also seen in following relations:
$n^a-1=(n-1)(1+n+n^2+ . . .+n^{a-1})$
$m^a-1=(m-1)(1+m+m^2+ . . .+m^{a-1})$
Finally the possible forms may be as follows:
$gcd(n^a-1, m^a-1)= gcd(n-1, m-1)$
Example: $n=4, m=7$ ⇒ $gcd(4^a-1, 7^a-1)=3$
$gcd(n^a-1, m^a-1)= gcd(n-1, 1+m+m^2+. . .+m^{a-1})$
Example: $n=32$, $m=2$, $a=5$ ⇒ gcd(32^5-1, 2^5-1)= 31
$gcd(n^a-1, m^a-1)= gcd(m-1, 1+n+n^2+. . . + n^{a-1})$
$gcd(n^a-1, m^a-1)= gcd[(1+m+m^2+. . .+m^{a-1}),(1+n+n^2+. . . + n^{a-1})]$
Example: $n=2$, $m=4$, $a=3$ ⇒ $gcd(2^3-1, 4^3-1)=7$
</s>