¿Qué es $\gcd(12345,54321)$?

Question

¿Qué es $\gcd(12345,54321)$?

Me di cuenta de que después de intentar $\gcd(12,21),\gcd(123,321),$ $\gcd(1234,4321)$ que son todos menos de o igual a $3$. Que me lleva a la pregunta de si hay una manera fácil de calcular dichos mayor de los divisores comunes.

Answer 1

Al $54321$ se divide por $12345$, el cociente es $4$ y el resto es $4941$: $$ 54321 = (4\times12345) + 4941. $$ Por lo tanto (como Euclides nos enseñó), $$ \gcd(12345,54321) = \gcd(12345,4941). $$ Al $12345$ se divide por $4941$, el cociente es $2$ y el resto es $2463$: $$ 12345 = (2\times4941) + 2463. $$ Por lo tanto $$ \gcd(12345,4941) = \gcd(2463,4941). $$ Y así sucesivamente. Seguir adelante hasta que esté hecho. (Los números de mantener cada vez menor, por lo que no puede durar siempre.) Y vas a encontrar en este caso no se necesita mucho más tiempo.

Answer 2

Sugerencia: Buscar en la suma de los dígitos de $12345$$54321$ , es divisible por $3$. Por lo $\ldots$

Answer 3

Con el fin de generalizar este limpiamente a valores superiores a $9$ dígitos, probablemente deberíamos pensar de $54321$$\sum_{k=1}^n k\cdot 10^{k-1}$$n=5$, por lo que al $n=11$ obtenemos $120987654321$, en lugar de, digamos, $110987654321$.

Asimismo, para $12345$ puede ser generalizado a $\sum_{k=1}^{n} (n-k+1) \cdot 10^{k-1}$. Al $n=11$ esto es $12345679011$, no $1234567891011$: nosotros comercio fuera de la idea de "escribir hacia atrás" para una mucho mayor algebraicas simplicidad.

Las formas cerradas de estas dos cantidades se $\frac1{81} (9n\cdot 10^n - 10^n + 1)$$\frac1{81} (10^{n+1} - 9n - 10)$, respectivamente. Así que si nos denota su MCD por $g$, entonces:

$$81g = (9n\cdot 10^n - 10^n + 1, 10^{n+1} - 9n - 10).$$

Vamos a tratar de acotar este. El término izquierda no es divisible por $10$: si multiplicamos por $10$, entonces el mcd se incrementará por un factor de $(n,10)$, por lo que

$$(n,10)\cdot81g = (9n\cdot 10^{n+1} - 10^{n+1} + 10, 10^{n+1} - 9n - 10) \\ = (9n\cdot 10^{n+1} - 10^{n+1} + 10 - (9n-1)\cdot(10^{n+1} - 9n - 10), 10^{n+1} - 9n - 10) \\ = (81n^2 + 81n, 10^{n+1} - 9n - 10).$$

Así, en particular,$g \le n(n+1)/(n,10)$, que es bastante pequeña en comparación con el tamaño de los números aquí. Sin embargo, es mucho más grande de lo $3$ o $9$ en la práctica: para $n=44$ es tan alto como $99$, y para$n=110$$1221$, sólo encuentro el límite superior!

Creo que usted podría ser capaz de reducir el MCD de expresión aún más el uso de binomio de expansión en $(1+9)^{n+1}$, pero se pone tipo de pelo.

Answer 4

$\newcommand{\ángulos}[1]{\left\langle\,{#1}\,\right\rangle} \newcommand{\llaves}[1]{\left\lbrace\,{#1}\,\right\rbrace} \newcommand{\bracks}[1]{\left\lbrack\,{#1}\,\right\rbrack} \newcommand{\dd}{\mathrm{d}} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\expo}[1]{\,\mathrm{e}^{#1}\,} \newcommand{\mitad}{{1 \over 2}} \newcommand{\ic}{\mathrm{i}} \newcommand{\iff}{\Leftrightarrow} \newcommand{\imp}{\Longrightarrow} \newcommand{\ol}[1]{\overline{#1}} \newcommand{\pars}[1]{\left(\,{#1}\,\right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\parcial #3^{#1}}} \newcommand{\raíz}[2][]{\,\sqrt[#1]{\,{#2}\,}\,} \newcommand{\totald}[3][]{\frac{\mathrm{d}^{#1} #2}{\mathrm{d} #3^{#1}}} \newcommand{\verts}[1]{\left\vert\,{#1}\,\right\vert}$ $$ \left\lbrace\begin{array}{rcrcrl} 54324 & = & 4\times 12345 & + & 4944 & \\ 12345 & = & 2\times 4944 & + & 2457 & \\ 4944 & = & 2\times 2457 & + & 30& \\ 2457 & = & 81\times 30 & + & 27& \\ 30 & = & 1\times 27 & + & \color{#f00}{\large 3} & \color{#f00}{\large\Leftarrow} \\ 27 & = & 9\times 3 & + & 0 & \end{array}\right. $$