Find $\gcd$ of $(2016)^{ 2017}-1$ and $(2016)^{ 2016}-1$

Question

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.

Answer 1

Hint:

Write $\;m^{m+1}-1=m(m^m-1)+m-1$.

Answer 2

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)

Answer 3

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

Answer 4

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.