¿Cuál es el máximo común divisor de: $$\underset{m}{\underbrace{111\dots111}}$$ and $$\underset{n}{\underbrace{111\dots111}}.$$ Supongo que esto implica el uso de algoritmo de Euclides (matriz-método).
Respuestas
¿Demasiados anuncios?
Sugerencia $\ $ El algoritmo de Euclides calcular el MCD de imitadores que para $\rm\: gcd(m,n)\:$.
Poner $\rm\ 1^{[n]}\: :=\ 1\cdots 1\ \ (n\ 1's)\ =\ (10^n-1)/9\:.\ $, a Continuación, su mcd es $\rm\ gcd(1^{[m]},\:1^{[n]}) $
Pero $\rm\ 1^{[m]}-1^{[n]}\ =\ 1^{[m-n]}\cdot 10^n\ \ \ $ [por ejemplo,$\rm\ 11111 - 111\ =\ 11000\ =\ 1^{[2]}\cdot 10^3\ $]
y $\rm\ gcd(10,1^{[n]}) = 1\ $ desde $\rm\ 9\cdot 1^{[n]}\ =\ 10^n-1\ $$\rm\ \rm\ gcd(10,\:10^n-1) = 1\:$.
Por lo tanto, la elección de la notación de modo que $\rm\:m\ge n\:,\ $ y la aplicación de las anteriores observaciones nos han
$ \rm\quad\ \ \ gcd(1^{[m]},1^{[n]})\ =\ gcd(1^{[m]}-1^{[n]},\:1^{[n]})\ =\ gcd(1^{[m-n]}\cdot 10^n,\:1^{[n]})\ =\ gcd(1^{[m-n]}\:,\:1^{[n]})$
Por lo $\rm\ \ gcd(1^{[m]},1^{[n]})\ =\ gcd(1^{[m-n]}\:,\:1^{[n]})\ $ como $\rm\ gcd(m,n)\ =\ gcd(m-n,n)\: $.
Por lo $\rm\ \ gcd(1^{[m]},1^{[n]})\ =\ 1^{[gcd(m,n)]}\ $ se sigue de la anterior por un simple inducción.
Comentario $\ $ total pruebas y más ver las respuestas a esta pregunta anterior, que probar
$$\rm \gcd(a^n\! - 1,\, a^m\! - 1)\ =\ a^{\gcd(n, m)}\! - 1 $$
El resultado de la siguiente manera por que se especializa $\rm\ a = 10,\ $ luego cancelar $\rm\:a\!-\!1 = 9.$
Shabaz
Puntos
403
