Find $\gcd$ of $(2016)^{ 2017}-1$ and $(2016)^{ 2016}-1$ Find $\gcd$ of $(2016)^{ 2017}-1$ and $(2016)^{ 2016}-1$? 
My teacher told me that $\gcd$ of $m^{m+1}-1$ and $m^m-1$ is $m-1$.
By using the above result I got $\gcd$ as $2015$. But I want to derive the above result. Please help me to derive the above result.
 A: Hint:
Write $\;m^{m+1}-1=m(m^m-1)+m-1$.
A: Hint $\ $ No insight insight is needed, just mechanically apply the Euclidean algorithm.
Note $\ {\rm mod}\,\ n^n\!-1\!:\,\ \color{#c00}{n^n}\equiv\color{#c00} 1\,\Rightarrow\, \color{#0a0}{n^{1+n}} =\, n\, \color{#c00}{n^n}\equiv\, \color{#0a0}n$
So by the Euclidean algorithm $\ (\color{#0a0}{n^{1+n}}\!-1,n^n\!-1) = (\color{#0a0}n-1,n^n-1) = n-1$
Remark $\  $ As a general rule of thumb, to simplify a gcd try modding out the largest argument by the smallest one (i.e. apply the reduction step in the Euclidean algorithm). As above, this may resolve the problem in a few steps (esp. for problems that were "designed" to be easy)
A: $(2016^{2017}-1)-(2016^{2016}-1)=$
$(2016^{2017})-(2016^{2016})=$
$2016\times{(2016^{2016})}-(2016^{2016})=$
$$(2016^{2016})*(2016-1)$$  Let $A=2016^{2017}
-1$,$B=2016^{2017}-1, C=2016^{2016}$.
As $gcd(A,C)=1,gcd(B,C)=1$  Therefore, $gcd(A,B)=2016-1=2015$  
A: Just to mention, a general result holds as follows:
$$\forall a > 1\text{, gcd}(a^m-1, a^n-1) = (a^{\text{gcd}(m,n)}-1)$$
where $m, n$ are positive integers.
Have fun proving this one now.
