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)
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$
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$