Cómo mostrar que$\gcd(a_1,a_2,\cdots,a_k) = 1$ implica que existe una solución no negativa para$\sum_{i=1}^{n}a_ix_i = n$ para grandes$n.$

Question

Estaba leyendo acerca de la Moneda-problema y no soy capaz de entender completamente el siguiente argumento:

Por otro lado, siempre que el MCD es igual a 1, el conjunto de números enteros que no puede ser expresado como una cónica combinación de $\{ a_1, a_2, …, a_n \}$ está limitada de acuerdo con el teorema de Schur, y por lo tanto el número de Frobenius existe.

Aquí, el autor argumenta a favor de la existencia de un no-negativos solución a los lineales de la ecuación de Diophantine (LDE) $$\sum_{i=1}^{k}a_ix_i =n \text{}$$ por lo suficientemente grande como $n.$ Ahora traté de entender que la prueba del teorema de Schur aquí entrar en el enlace de la descripción aquí (Página 98), pero no estoy seguro que me entienden. En particular, no entiendo por qué la generación de la función asociada con la secuencia de $h_n$ que cuenta el número de soluciones para el LDE es $$H(x)= \prod_{i=1}^{k}\left(\frac{1}{1-x^{a_i}}\right).$$

Una vez que hemos $H(x)$ podemos deducir que $$h_n\sim \frac{n^{k−1}}{(k − 1)!a_1a_2 ··· a_k}$$ como $n\to \infty.$ ¿Cómo funciona esto exactamente muestran que por lo suficientemente grande como $n,$ $h_n>0?$ Es porque el $\frac{n^{k−1}}{(k − 1)!a_1a_2 ··· a_k}>0?$

Answer 1

Un enfoque simple para el título de:

Gracias a Bezout, hay algunos (no necesariamente) entero combinación de la $a_i$s que hace $1$. Añadir una lo suficientemente grande como varios de $a_1$ a cada coeficiente de hacer es no negativo y llamar a la suma de $k$; tenemos $k\equiv 1 \pmod{a_1}$.

Ahora cualquier número $\ge ka_1$ no es una combinación negativa de la $a_i$s. Es decir, vamos a $n$ ser el número deseado, y deje $m=n\bmod a_1$. A continuación, $mk$ es positivo combinación, y podemos añadir algún múltiplo de $a_1$ hacer $n$ , ya $mk\equiv n\pmod{a_1}$ e $mk<n$ porque $m<a_1$.

Answer 2

Primero hacemos esto para $k =2$.

Supongamos WLOG que $a_1 < a_2$. Si gcd$(a_1,a_2)=1$ entonces $a_2 \mod a_1 \in \left(\mathbb{Z}/a_1 \mathbb{Z}\right)^{\times}$. De modo que existe un inverso multiplicativo $m_2 \in \left(\mathbb{Z}/a_1 \mathbb{Z}\right)^{\times}$ de $a_2$; o, equivalentemente, existe una nonegative entero $m_2 < a_1$ tal que $m_2 \times a_2 \equiv_{a_1} 1$. Esto implica lo siguiente: existe enteros $m_2$ e $m_1$; $|m_2| < a_1$ e lo $|m_1| \leq a_2+1$ tal que $m_2a_2 = 1 + m_1a_1$, o lo que es equivalente, $m_2a_2-m_1a_1 = 1$.

Así que vamos a $y$ ser lo suficientemente grande entero, y deje $k \in \{0,1,\ldots, a_1-1\}$ ser tal que $Na_1 + k = y$. A continuación, $Na_1 +k(m_2a_2-m_1a_1) = y$, y $N-km_1$ es positivo si $N > km_1$, donde $k < a_1$ e $m_1 \leq a_2+1$. Esto mantendrá si $y$ al menos $a_1(a_1+1)(a_2+1)$. Esto completa el caso de $k=2$.

Habiendo establecido esto para $k=2$ ahora usamos la inducción para demostrar que esto representa para general $k$. En particular, vamos a $\{a_1,a_2,\ldots, a_{k+1}\}$ ser un conjunto de enteros positivos, donde el máximo común divisor es 1. Nos muestran el uso de la inducción en $k$ que cada entero $Y$ puede ser expresado $Y = \sum_{i=1}^{k+1} M_ia_i$. Para este fin, vamos a $c =$mcd$(a_k,a_{k+1})$. Luego, por inducción, por cualquier suficientemente grande entero $y$, hay nonegative enteros $M_k$ e $M_{k+1}$ tal que $M_ka_k+M_{k+1}a_{k+1} = cy$. Así que elija $y$ suficientemente grande tal que mcd$(a_1,\ldots, a_{k-1}, cy) = 1$; de hecho, cualquier $y$ suficientemente grandes satisfacciones mcd$(a_1,\ldots, a_{k-1}, y) = 1$ va a hacer [asegúrese de que usted ver por qué], y, de hecho, hay un entero positivo $y$ [asegúrese de que usted ver por qué].

Entonces, por la hipótesis inductiva para cualquier suficientemente grande entero $Y$ existen nonegative enteros $M_1,\ldots, M_{k-1}, M_y$ tales que $cyM_y + \sum_{i=1}^{k-1} M_ia_i = Y$, $cy$ sí satisface $cy = M_ka_k+M_{k+1}a_{k+1}$ el resultado de la siguiente manera.

---

ETA: sin EMBARGO, hacemos notar que, establecimiento $A = \max \{a_1,\ldots, a_k\}$ que podemos asumir WLOG que $k \leq 1+\log A$. O más precisamente, no es un subconjunto $S$ de $\{1,\ldots, k\}$ de cardinalidad $\log A$ tales que mcd$\{a_i; i \in S\}$ es 1. Entonces bastaría para mostrar que cada gran cantidad $Y$ puede ser escrito $Y=\sum_{i \in S} M_ia_i$ donde cada una de las $M_i$ es un entero no negativo.

De hecho, cada una de las $a_i$ se puede escribir como un producto de en la mayoría de las $\log A$ números primos. Por lo tanto, construir un conjunto $a_{i_1},a_{i_2},a_{i_l}; l \leq 1+\log A$ tales que mcd$\{a_{i_1},\ldots, a_{i_l}\} = 1$. Supongamos que el uso de la inducción, que mcd$\{a_{i_1},\ldots, a_{i_j}\}$ es un número compuesto, que tiene en la mayoría de las $\log A -j+1$ factores primos $p_1\ldots p_{\log A-j}$. Entonces existe un $a_i$ tal que al menos uno de $p_1,\ldots, p_{\log A-j+1}$ no divide $a_i$. Entonces mcd$\{a_{i_1},\ldots, a_{i_j}, a_i\}$ es un número compuesto, que tiene en la mayoría de las $\log A -j$ factores primos.