¿Cómo encontrar todos los posibles valores que pueden formarse con dos enteros A y B usando solo el operador +/- cualquier número de veces?

Question

Dados dos números A y B, ¿cómo encontrar todos los números en un rango grande digamos 'k' que se puedan formar sumando o restando A y B juntos cualquier cantidad de veces?

Ejemplo: Supongamos que los números son 3 (A) y 8 (B). Deseamos encontrar todos los números hasta 4 (k) que se puedan formar.

En este ejemplo todos los números se pueden formar.

1 = 3+3+3-8

2 = 8-3-3

3 = 3

4 = 8+8-3-3-3-3

Creo que todos los números que son divisibles por el MCD de A y B se pueden formar. Pero no puedo probarlo. Lo intenté en muchas entradas y vi que funciona, aún así no pude encontrar una prueba. No sé si estoy en lo correcto o equivocado. ¡Ayúdame!

Answer 1

Felicitaciones por descubrir un problema importante y formular la conjetura correcta!

En lugar de hablar de suma y resta, podemos preguntar lo siguiente. Se nos dan dos enteros $a$ y $b$, no ambos $0$. ¿Qué enteros positivos se pueden expresar en la forma $ax+by$, donde $x$ e $y$ son enteros (no necesariamente positivos)? Llamamos bueno a un entero positivo que se pueda expresar de esta manera.

Es claro que hay algunos enteros positivos expresables en la forma $ax+by$, por lo que hay buenos enteros positivos. Sea $d$ el menor entero positivo bueno. Mostraremos que $d$ es el máximo común divisor de $a$ y $b.

El paso principal para hacer esto es demostrar que $d$ divide a $a$ y que $d$ divide a $b. Demostramos que $d$ divide a $a. La prueba de que $d$ divide a $b$ es esencialmente la misma.

Dado que $d$ es bueno, se sigue que $d=au+bv$ para algunos enteros $u$ y $v.

Intentamos dividir $a$ por $d$. Obtenemos $$a=qd+r,$$ donde $q$ es el cociente y donde el "resto" $r$ satisface $0\le rmenor entero positivo bueno, y $r

Además, $d$ es el mayor entero positivo que divide tanto a $a$ como a $b. Si $z$ divide a $a$ y a $b, entonces, dado que $d=au+bv$, tenemos que $z$ divide a $d, y por lo tanto $z \le d.

Ahora que sabemos que el máximo común divisor $d$ de $a$ y $b$ se puede expresar en la forma $ax+by$, es fácil ver que cualquier múltiplo positivo $kd$ de $d$ también se puede expresar en la forma $ax+by$.

Observación: Hay un importante bono teórico aquí. Hemos demostrado que para cualquier enteros positivos $a$ y $d$, existe un entero positivo $d$ tal que $d$ divide a $a$ y a $b, y tal que cualquier $z$ que divida a $a$ y a $b$ debe dividir a $d. Esto es ciertamente cierto para los enteros pequeños con los que estamos familiarizados, pero no es evidente que el resultado sea válido para todos los enteros positivos. Ahora sabemos que sí.

Observación: Hay otros enfoques para una demostración que en un sentido práctico son más informativos. Sean $a$ y $b$ enteros muy grandes cuyo máximo común divisor es $1$, como $2^{50}$ y $3^{37}$. Por el argumento anterior, hay enteros $x$ e $y$ tales que $ax+by=1. Hay situaciones prácticas en las que queremos encontrar explícitamente tales números $x$ e $y. Eso se puede hacer de manera muy eficiente usando el Algoritmo Extendido de Euclides. Las ideas que llevan a este algoritmo dan una prueba alternativa del resultado sobre el que trata tu publicación.

Las ideas que llevaron a la prueba se pueden generalizar sustancialmente. Por ejemplo, supongamos que $A(t)$ y $B(t)$ son polinomios (por ejemplo, con coeficientes reales) tales que no hay un polinomio de grado $\geq 1$ que divida a ambos $A(t)$ y $B(t)$. Entonces existen polinomios $X(t)$ y $Y(t)$ tales que $A(t)X(t) + B(t)Y(t)$ es idénticamente igual a $1$. La prueba de este hecho importante es, en su estructura básica, muy similar a la prueba que dimos anteriormente.