Combinación lineal de los números naturales positivos de los coeficientes de

Question

Estoy buscando una referencia para el siguiente resultado, así como para evitar la escritura de una prueba plena en un papel. Alternativamente, si un one-liner existe, me encantaría saber de ti!

Teorema: Vamos a $a, b$ ser de dos enteros positivos. Entonces existe un conjunto finito $N$ de los enteros positivos menores que $\mbox{lcm}(a, b)$ tal forma que: $$\{k_1a + k_2b \mid k_1, k_2 \in \mathbb{N}\} = \{\mbox{lcm}(a, b) + k\times\gcd(a, b) \mid k \in \mathbb{N}\} \cup N.$$

Yo también estoy interesado en su generalización a cualquier número de enteros: Decir un conjunto de números enteros es un conjunto lineal con $n$ periodos de si puede ser escrita como: $$\{c_0 + \sum_{i=1}^n k_i \times c_i \mid k_i \in \mathbb{N}\}.$$ Entonces:

Teorema: Cualquier lineales conjunto es la unión de un conjunto finito y un conjunto lineal con un período.

Gracias!

Answer 1

Algunas variantes de la siguiente resultado queda demostrado en la mayoría de los libros en la escuela primaria de la teoría de números.

Teorema: Vamos a $a$ $b$ ser relativamente primer enteros positivos. Si $c >ab$, entonces no existen números enteros positivos $x$ $y$ tal que $ax+by=c$.

La prueba no es difícil. No es un one-liner, en gran parte porque no soy un hombre de pocas palabras.

Existen enteros $x_0,y_0$, de tal manera que $ax_0+by_0=c$. En consecuencia, todo entero soluciones de la ecuación de $ax+by=c$ tienen la forma $x=x_0+bt$, $y=y_0-at$, donde $t$ rangos de los números enteros. Para producir una solución positiva, queremos encontrar a $t$ tal que $x>0$$y>0$.

Así que necesitamos $y_0-at >0$, $x_0+bt>0$, o, equivalentemente, $$-\frac{x_0}{b}<t <\frac{y_0}{a}.$$ El intervalo de $(-x_0/b,y_0/a)$ tiene la anchura $y_0/a+x_0/b$. que se simplifica a $(ax_0+by_0)/ab$, $c/ab$. Si $c/ab>1$, el intervalo está garantizado para contener un entero $t$, y hemos terminado.

Si $a$ $b$ no son relativamente primos, vamos a $d=\gcd(a,b)$, y vamos a $a=da'$, $b=db'$. Deje $c$ ser un múltiplo de $d$, decir $c=c'd$. Entonces si $c'>a'b'$, $c$ es representable como una combinación lineal de $a$$b$. De forma equivalente, todas las múltiples$c$$d$, que es mayor que $ab/d$ es una combinación lineal positiva de $a$$b$.

En particular, el $\text{lcm}(a,b)$ plazo en su expresión nos pone pasado los números que no tienen una representación positiva. El enlazado $ab/d$ es muy fuerte.

La generalización a "muchos períodos" es sencillo. Llegar sharp límites en el número más pequeño $m$ de manera tal que todos los $c$ que satisfacer la necesaria condición de divisibilidad son representables puede no ser fácil.

Answer 2

Deje $c_1,\dots,c_n$ ser enteros positivos y establecer $a=\gcd(c_1,\dots,c_n)$. Por la identidad de Bézout, podemos escribir $a=\sum_{i=1}^n z_i c_i$ para enteros $z_i$.

Dejando $c=\sum_{i=1}^n c_i$, cada múltiplo $N$ $a$ puede ser escrito como $N=qc+ra$ donde $q,r$ son enteros con $0\leq r<c/a$.

Si $N$ es lo suficientemente grande, en particular si $N\geq c+\max_i |z_i|c^2/a$, entonces los coeficientes en $N=\sum_{i=1}^n (q+z_ir) c_i$ son todos no negativos. Es decir, todos los grandes múltiplo de $a$ puede ser escrito $N=\sum_{i=1}^n k_i c_i$ para enteros no negativos $k_i$.

Es decir, $$\{c_0 + k a\mid k \in \mathbb{N}\}\setminus \{c_0 + \sum_{i=1}^n k_i c_i \mid k_i \in \mathbb{N}\}$$ es un conjunto finito.

Answer 3

El artículo de la wikipedia sobre numérico semigroups contiene varias referencias que te pueden ayudar. También recomiendo una respuesta por Robjohn a otra pregunta aquí en el MSE. La pregunta era acerca de un caso particular, pero Robjohn cubierto el caso general de una numérico semigroup generado por dos coprime números muy muy bien.