Entero más grande que no puede ser representado como un no-negativo combinación lineal de $m, n = mn - m - n$? Por qué?

Question

Esta aparentemente sencilla pregunta realmente ha sacado de mí:

¿Cómo puedo probar que el entero más grande que no puede ser representado con un no-negativo combinación lineal de los números enteros $m, n$$mn - m - n$, asumiendo que son coprime?

Llegué tan lejos como este, pero ahora no puedo averiguar dónde ir:

$mx + ny = k$ donde $k = mn - m - n + c$, para algunas de las $c > 0$

$\Rightarrow m(x + 1) + n(y + 1) = mn + c$

Si sólo pudiera probar este debe tener un valor no negativo solución para$x$$y$, me gustaría hacer... pero estoy un poco atascado.

Alguna idea?

Answer 1

He aquí una alternativa (pero quizás más peatonal) prueba:

(a) $mn-m-n$ no es un valor no negativo combinación lineal: se supone que, por el contrario, que $mn-m-n=am+bn$$a,b\in\mathbb N_0$. Entonces $$(a+1)m+bn=mn-n=(m-1)n$$ $$(a+1)m = (m-1-b)n$$ Pero $(a+1)m$ es claramente positiva y desde $(a+1)m < mn-n < mn$, es un número positivo menor que $mn$ que es un múltiplo de ambos $m$$n$, contradiciendo la suposición de que ese $m$ $n$ son coprime.

(b) Cada entero $k>mn-m-n$ es un valor no negativo combinación lineal. El $m$ números $0$, $n$, $2n$, ..., $(m-1)n$ representan a todas las diferentes clases de residuos modulo $m$, por lo que uno de ellos debe ser congruente a $k$ modulo $m$. Por lo $k=am+bn$ donde $0\le b<m$, y tenemos que comprobar que $a$ es no negativo. Sin embargo, si $a$ es negativo, $am+bn$ puede ser en la mayoría de las $(m-1)n-m = mn-m-n$.

Answer 2

Deje $m$ $n$ ser positivo y relativamente primos. Nos muestran que $mn$ es el mayor entero que no puede ser representada como un positivo combinación lineal de $m$$n$, que es, como $mx+ny$ donde $x$ $y$ son enteros positivos. Podemos entonces deducir el resultado correspondiente para no negativo de las combinaciones lineales. Hay más sencillo pruebas, pero la de abajo se adapta de forma natural hacia el comienzo de un curso en la escuela primaria de la teoría de números.

La prueba consta de dos partes: (i) $mn$ no puede ser representado como una combinación lineal de $m$$n$, y (ii) todo número entero mayor que $mn$ puede ser expresado como una combinación lineal de $m$$n$.

No Representabilidad de $mn$: Supongamos que al contrario que $mn=mx+ny$ donde $x$ $y$ son positivos. A continuación,$mx=n(m-y)$. Tenga en cuenta que $m$ divide $n(m-y)$ $m-y$ es positivo. Desde $m$ $n$ son relativamente primos, se deduce que el $m$ divide $m-y$. Esto es imposible, ya $m>m-y>0$.

Representatividad de todos los números enteros $>mn$: Vamos a $w$ ser un número entero mayor que $mn$. Nos muestran que $w$ es representable.

Desde $m$ $n$ son relativamente primos, algunos entero combinación lineal de $m$ $n$ es igual a $1$. Multiplicando por $w$, podemos encontrar enteros $x_0$, $y_0$ tal que $$mx_0+ny_0=w.$$

Ahora vamos a $t$ ser cualquier número entero. Es fácil comprobar que $$m(x_0-tn)+ n(y_0+tm)=w.$$ Vamos a demostrar que podemos elegir $t$, de modo que $x_0-tn$ $y_0+tm$ son positivos. A continuación, ajuste de $x=x_0-tn$ $y=y_0+tm$ nos dará la representación deseada.

Queremos elegir a $t$ tal que $tn<x_0$$tm>-y_0$. Así queremos encontrar $t$ tal que $$-\frac{y_0}{m} <t < \frac{x_0}{n}.$$

Para demostrar que podemos encontrar un entero $t$, nos fijamos en la diferencia $$\frac{x_0}{n}-\left(-\frac{y_0}{m}\right).$$ Pero $$\frac{x_0}{n}-\left(-\frac{y_0}{m}\right)=\frac{mx_0+ny_0}{mn}=\frac{w}{mn}>1.$$ Ya que el intervalo $$-\frac{y_0}{m} <t < \frac{x_0}{n}$$ tiene una longitud mayor de $1$, contiene al menos un entero $t$. Esto completa la prueba.

De la misma forma, podemos mostrar que si $w>kmn$, entonces la ecuación de $mx+ny=w$ tiene al menos $k$ soluciones positivas.

La representabilidad el uso de no-negativo $x$ $y$ : es fácil ver que $w$ es representable mediante números enteros positivos si y sólo si $w-m-n$ es representable mediante enteros no negativos. De ello se desprende que $mn-m-n$ es el mayor número que no es representable mediante enteros no negativos.

Answer 3

Sugerencia Normalizar $\,k = m\, x + n\, y\,$ $\,0 \le x < n\,$ mediante la adición de un múltiplo de $\,(-n,m)\,$ $\,(x,y).$

Lema $\ \ k = m\ x + n\ y\,$ para algunos enteros $\,x,\,y \ge 0\,$ $\iff$ su normalización ha $\,y \ge 0.$

Prueba de $\ (\Rightarrow)\ $ Si $\ x,\, y \ge 0,\,$ normalización añade $\,(-n,m)\,$ cero o más veces, la preservación de la $\,y \ge 0.\,$
$(\Leftarrow)\ \,$ Si la normalizado rep $\ y < 0,\,$ $\,k\,$ no tiene representación con $\ x,\,y \ge 0,\,$ ya que a cambio de lo que $\,y > 0\,$ debemos agregar $\,(-n,m)\,$ al menos una vez, que las fuerzas de $\,x < 0.\ \ $ QED

Por último, observe que desde $\ k = m\, x + n\, y\ $ va en aumento tanto en $\,x\,$ $\,y,\,$ es claro que el más grande no-representable $\,k\,$ ha normalización $\,(x,y) = (n\!-\!1,-1),\,$ es decir, el entramado punto en que está situada más a la derecha (max $\,x$) y superior (max $\,y$) en el nonrepresentable mitad inferior $(y < 0)$ de la normalizado de la tira, es decir, la franja vertical donde $\, 0\le x \le n-1.$ $\,(x,y) = (n\!-\!1,-1)\,$ rendimientos $\, k = m\,(n\!-\!1)+n\,(-1) = m\,n - m - n\ $ es el más grande de esa representación. $\ \ $ QED

Aviso de que la prueba tiene una vívida imagen geométrica: representaciones de $\,k\,$ corresponden a la celosía puntos de $\,(x,y)\,$ en la línea de $\, n\, y + m\, x = k\,$ con pendiente negativa $\, = -m/n.\,$ La normalización se consigue desplazando hacia adelante/hacia atrás a lo largo de la línea por múltiplos de los vectores $\,(-n,m)\,$ hasta que uno cae en la normal de la tira donde $\,0 \le x \le n\!-\!1.\,$ Si la normalizado rep $\,y\ge 0\,$ luego de que estamos hecho; de lo contrario, por el lema, $\,k\,$ no tiene rep con tanto $\,x,y\ge 0.\,$ Este es un discreto análogo al hecho de que, en el plano de la $\,\mathbb R^2,\,$ una línea de pendiente negativa tiene puntos en el primer cuadrante $\,x,y\ge 0\ $ iff su $\,y$-interceptar $\,(0,\,y_0)\,$ se encuentra en el primer cuadrante, es decir, $\, y_0 \ge 0.$

Hay mucha literatura sobre este clásico problema. Para encontrar trabajo usted debe asegurarse de que usted busca en muchos alias, por ejemplo, la estampilla problema, Sylvester/Frobenius problema, Diophantine problema de Frobenius, Frobenius conductor, cambiar de dinero, cambio de moneda, cambio de hacer problemas, h-base asintótica y bases con el aditivo de la teoría de los números, entero de programación de los algoritmos y de los cortes de Gomory, mochila de problemas y algoritmos voraces, etc.

Answer 4

He aquí otra versión de la prueba. Hacer una tabla de los números enteros no negativos en las filas de tamaño $m$, luego marca la primera $m$ múltiplos de $n$ (desde 0 hasta, pero no incluyendo $mn$). Por ejemplo, si $m=4$$n=7$, tenemos la siguiente tabla con los 4 primeros múltiplos de 7 marcados con un * :

$$\begin{array} & 0* & 1 & 2 & 3 \\ 4 & 5 & 6 & 7* \\ 8 & 9 & 10 & 11 \\ 12 & 13 & 14* & 15 \\ 16 & 17 & 18 & 19 \\ 20 & 21* & 22 & 23 \\ 24 & 25 & 26 & 27 \\ 28 & 29 & 30 & 31 \\ \ldots \end{array}$$

Ahora observe:

1. Cada columna tiene exactamente un valor marcado. (Esto se deduce de (m,n)=1.)
2. Los valores marcados, y todos los valores a continuación en la misma columna, son todos representable como no-negativa de combinaciones lineales de $m$$n$.
3. Por el contrario, cualquier representable entero no negativo, $mx+ny$ se encuentra en o por debajo del valor marcado en su columna. (Para $mx+ny$ debe $x$ filas por debajo del valor de $ny$, que es un múltiplo de a $n$ y por lo tanto se encuentra en o por debajo de un valor marcado.)

Por lo tanto, el más grande no-representable número se encuentra una fila de arriba el mayor número marcado. Esto es $(m-1)n -m = mn - n -m$.

Answer 5

Creo que la manera más fácil para obtener la idea es la siguiente. A continuación se presentan dos básica de hechos que llevan casi de inmediato la respuesta. Suponga que $m&ltn$$s=0\ldots(n-1)$.

1. Si $nk+s$ es representable como un no-negativo combinación lineal de $m$$n$, luego $n(k+1)+s$, $n(k+2)+s$ etc. son representables así.

2. Si $nk+s$ es el mínimo número positivo de esta forma que es representable como un no-negativo combinación lineal de $m$$n$, $nk+s=mt$ positivos $t$ (de hecho, de lo contrario si $nk+s=mt+nu,u>0$, entonces podemos restar $n$, e $n(k-1)+s$ todavía ser representable).

Ahora, a partir de estos dos hechos: para cada una de las $s=0\ldots(n-1)$ podemos encontrar al menos $t_s$ tal que $mt_s\equiv s \mod n$, y si $t_{s'}$ es el más grande de entre todos los $t_s$'s, a continuación, $mt_{s'}-n$ es el mayor número que puede ser representado como un no-negativo de la combinación lineal. Desde $m$ $n$ son coprime, hay una correspondencia uno a uno entre el$t_s\in\{1,\ldots,n-1\}$$s\in\{1,\ldots,n-1\}$, e $t_{s'}=n-1$$s'=n-m$. Por lo tanto, el más grande no-representable número es $m(n-1)-n=mn-m-n$.