Encuentre $\gcd$ de $(2016)^{ 2017}-1$ y $(2016)^{ 2016}-1$

Question

Encuentre $\gcd$ de $(2016)^{ 2017}-1$ y $(2016)^{ 2016}-1$ ? Mi profesor me dijo que $\gcd$ de $m^{m+1}-1$ y $m^m-1$ es $m-1$ . Utilizando el resultado anterior he obtenido $\gcd$ como $2015$ . Pero quiero obtener el resultado anterior. Por favor, ayúdame a derivar el resultado anterior.

Answer 1

Pista:

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

Answer 2

Sugerencia $\ $ No se necesita ninguna perspicacia, basta con aplicar mecánicamente el algoritmo euclidiano.

Nota $\ {\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$

Así que por el algoritmo euclidiano $\ (\color{#0a0}{n^{1+n}}\!-1,n^n\!-1) = (\color{#0a0}n-1,n^n-1) = n-1$

Observación $\ $ Como regla general, para simplificar un gcd intente modificar el argumento mayor por el menor (es decir, aplique el paso de reducción del algoritmo euclídeo). Como en el caso anterior, esto puede resolver el problema en unos pocos pasos (especialmente para problemas que fueron "diseñados" para ser fáciles).

Answer 3

$(2016^{2017}-1)-(2016^{2016}-1)=$ $(2016^{2017})-(2016^{2016})=$ $2016\times{(2016^{2016})}-(2016^{2016})=$ $$(2016^{2016})*(2016-1)$$ Sea $A=2016^{2017} -1$ , $B=2016^{2017}-1, C=2016^{2016}$ . En $gcd(A,C)=1,gcd(B,C)=1$ Por lo tanto, $gcd(A,B)=2016-1=2015$

Answer 4

A modo de ejemplo, se puede citar el siguiente resultado general:

$$\forall a > 1\text{, gcd}(a^m-1, a^n-1) = (a^{\text{gcd}(m,n)}-1)$$

donde $m, n$ son enteros positivos.

Diviértete probando esto ahora.