Dado $a,b$ ¿Cuál es el número máximo que no se puede formar con $na + mb$ ?

Question

Por ejemplo, dados dos números $5$ y $6$ el número máximo es $19$ como después de $19$ cada número puede formarse mediante la ecuación $5n+6m$ poniendo diferentes valores (no negativos) para $n$ y $m$ .

Este número no es posible para $4$ & $6$ .

No estoy seguro de cómo seguir adelante. Lo único que tengo hasta ahora es que el número es posible sólo si los números dados son pseudo-primos. Se agradece cualquier ayuda.

Answer 1

Aquí hay un extracto de uno de mis antiguos posts de sci.math que explica un punto de vista geométrico.

Obsérvese que podemos normalizar cualquier representación $\rm\ N\ =\ P\ X + Q\ Y\ $ para que $\rm\ 0 \le X < Q\ $ añadiendo un determinado múltiplo integral de $\rm\ (-Q,P)\ $ a $\rm\,(X,Y).\ $ De esta observación se desprende lo siguiente

Lema $\rm\ \ N = P\ X + Q\ Y\ $ para algunos enteros $\rm\ X,Y \ge 0\ $ si su normalización tiene $\rm\, Y \ge 0$ .

Prueba $\rm\ \ \ X,Y \ge 0\ $ implica que la normalización requiere la adición de $\rm\,(-Q,P)\,$ cero o más veces, $\ $ y esto preserva la condición $\rm\, Y \ge 0.\ $ Por el contrario, si la normalización tiene $\rm\, Y < 0,\ $ entonces $\rm\,N\,$ no tiene representación con $\rm\ X, Y \ge 0,\ $ porque para cambiar $\rm\, Y > 0\, $ requiere añadir $\rm\ (-Q,P)\ $ al menos una vez, lo que cambia $\rm\, X < 0.\ $ Por último, dado que $\rm\ X\ P + Y\ Q\ $ está aumentando en ambos $\rm\, X,Y,\ $ está claro que el mayor número no representable $\rm\, N\,$ tiene normalización $\rm\, (X,Y)\ =\ (Q-1,-1),\, $ por lo tanto $\rm\ N\ =\ PQ - P - Q.\quad $ QED

Obsérvese que la prueba tiene una representaciones de $\rm\,N\,$ corresponden a los puntos de la red $\rm\,(X,Y)\,$ en la línea $\rm\ N = P\ X + Q\ Y\ $ con pendiente negativa $\rm = -P/Q.\ $ La normalización se consigue desplazando hacia delante/atrás a lo largo de la línea por múltiplos integrales del vector $\rm\,(-Q,P)\,$ hasta aterrizar en la franja normal donde $\rm\ 0 \le X < Q-1.\ $ Desde este punto de vista, la prueba queda muy clara.

En caso de que te interese, la clase que estoy dando es de álgebra lineal, pero como puedes ver me gusta dar rompecabezas a la clase que no son necesariamente relacionados con la materia (de forma obvia).

Aquí la estructura lineal subyacente es una $\mathbb Z$ -módulo, una generalización de un espacio vectorial; es decir, aquí los escalares son los enteros, por lo que sólo tienen la estructura de un anillo, no de un campo. A no ser que ya se haya enseñado teoría de módulos, puede ser difícil explicar con precisión explicar la relación con los espacios vectoriales.

Por último, cabe mencionar que ha habido muchas escrito sobre este problema clásico. Para localizar estos trabajos debe asegurarse de buscar en los numerosos alias, por ejemplo, problema del sello postal, problema de Sylvester/Frobenius, problema diofantino de Frobenius, conductor de Frobenius, problemas de cambio de dinero, de cambio de monedas, de cambio de moneda, bases h y bases asintóticas en la teoría aditiva de los números, algoritmos de programación entera y cortes de Gomory, problemas de knapsack y algoritmos codiciosos, etc.

Answer 2

La fórmula general para el coprimo $a$ y $b$ es que se pueden hacer todos los números de $(a-1)(b-1)$ hacia adelante, pero hay números anteriores a él que no pueden hacerse como tales múltiplos enteros positivos.

Comienza observando que para los coprimos $a$ y $b$ podemos escribir $1 = na + mb$ para algunos $n,m \in \mathbb{Z}$ . Así, para un número entero $x$ tenemos $x = nxa + mxb$ . Ahora reste o añada $0 = a*b - b*a$ a ambos lados de la ecuación para que los coeficientes sean positivos

Answer 3

Dejemos que $\let\leq\leqslant\let\geq\geqslant m\in\mathbb N$ y $\gcd(a,b)=1$ . Bézout ya nos da $x,y$ con $xa+yb=m$ pero pueden ser negativos. Porque queremos controlar $x$ y $y$ simultáneamente podríamos idear un herramienta que vincula esos dos términos. Un enfoque para hacer que los términos $xa$ y $yb$ se parezcan es haciendo que ambos casi múltiplos de $\color{blue}{ab}$ .

He aquí cómo: escriba $x=q_1b+r_1$ y $y=q_2a+r_2$ con $0\leq r_1<b$ y $0\leq r_2<a$ .
Tenemos $$\begin{align*}n=xa+yb&=(q_1\color{blue}{ab}+r_1a)+(q_2\color{blue}{ab}+r_2b)\\ &=(q_1+q_2)\color{blue}{ab}+r_1a+r_2b.\end{align*}$$

La mayor parte del trabajo ya está hecho.

Observar $r_1a+r_2b\leq a(b-1)+b(a-1)$ por lo que para $n>a(b-1)+b(a-1)$ tenemos $q_1+q_2>0$ . (Esto demuestra que existe un máximo). Esto debería permitir que los $n$ para que se escriba como se quiere, porque $$\begin{align*}n-ab=(q_1+q_2-1)ab+r_1a+r_2b\qquad&\text{with }q_1+q_2-1\geq0\\&\text{if }n>a(b-1)+b(a-1).\end{align*}$$

En efecto: dejemos que $g=a(b-1)+b(a-1)-ab$ y $n>g$ . Entonces $n+ab$ puede escribirse como $$n+ab=(q_1+q_2)ab+r_1a+r_2b\qquad\text{with }q_1+q_2\geq1$$ por lo que $$n=(q_1+q_2-1)ab+r_1a+r_2b\qquad\text{with }q_1+q_2-1\geq0.$$

Así que todo $>g$ puede escribirse con coeficientes positivos (por ejemplo, tomando juntos $a\cdot r_1$ y $a\cdot b(q_1+q_2-1)$ ).

$g=ab-a-b$ es un límite inferior
De hecho, si $ab-a-b=ax+by$ entonces $a\mid y+1$ pero $ax+by\geq0+b(a-1)>g$ contradicción.

---

Nota: esta técnica permite demostrar en general que el mayor número no representable es $$g(a_1,\ldots,a_n)\leq(n-1)a_1\cdots a_n-(a_1+\cdots+a_n).$$ Este límite superior es exacto para $n=2$ pero débil para $n>2$ .