Número de enteros positivos que no se puede expresar como $ax+by$

Question

Probar que hay exactamente

$$\displaystyle{\frac{(a-1)(b-1)}{2}}$$

enteros positivos que no puede ser expresado en forma

$$ax\hspace{2pt}+\hspace{2pt}by$$

donde $x$ y $y$ son números enteros no negativos, y $a, b$ son enteros positivos tales que $\gcd(a,b) =1$.

Answer 1

Sugerencias: probar

Si $ax+by=c$ y divide a $ax'+by'=c$, entonces el $b$ $x-x'$, y divide a $a$ $y-y'$ y $(x-x')/b=(y'-y)/a$.

$n$ puede ser expresado solamente si $((a-1)(b-1)/2)-1-n$ no.

Answer 2

Llamar a un número entero malo , si no puede ser representado como un entero combinación de $a$ $b$ con un valor no negativo de los coeficientes. Hay $(a-1)(b-1)$ enteros no negativos a menos de $(a-1)(b-1)$, y sabes que todos los de la de la mala enteros están entre ellos. Echa un vistazo a un ejemplo sencillo. Supongamos que $a=4$$b=7$, por lo que los malos números enteros debe estar entre $0$ $17$ incluido.

$$\begin{array}{r|c} \text{Good}:&0&16&15&14&4&12&11&7&8\\ \hline \text{Bad}:&17&1&2&3&13&5&6&10&9 \end{array}$$

Observe que los números en cada columna suman a $17=(a-1)(b-1)-1$. Un poco de experimentación sugieren que este es un fenómeno general: si $b=(a-1)(b-1)-1$ es el mayor mal entero, y $0\le n\le b$, exactamente uno de $n$ $b-n$ es mala. Si usted puede probar esto, usted tendrá como consecuencia inmediata que el $\frac12(b+1)=\frac12(a-1)(b-1)$ enteros son malos.

Es fácil ver que $n$ $b-n$ no puede ser bueno: que harían $b$ buena. Por lo tanto, usted quiere demostrar que también puede ser malo. Para esto usted probablemente quiera usar lo que sabes acerca de la solución general de la ecuación de Diophantine $c=ax+by$. Si te quedas atascado, echa un vistazo a la prueba del Lema 3 en este documento por Mike spivey se; no es exactamente lo que quiere, pero está muy cerca y te dará las ideas que usted necesita para completar el argumento.

Answer 3

Es bien sabido que cualquier número $\ge (a-1)(b-1)$ es representable.

El número de números de $c$ tal que $0 \lt c \lt ab$ que son representables se corresponden exactamente con el número de celosía puntos de la región

$ax + by \lt ab$, $x \ge 0$, $y \ge 0$

Esto es porque si $ax + by = ax' + by'$, $x-x'$ es divisible por $b$, lo que no puede suceder en la región, por lo que dos de celosía puntos representan números diferentes (y viceversa).

Un directo a contar el argumento de que ahora le da lo que usted busca. Tenga en cuenta que usted necesita hacer algunos resta para obtener el número de números que no representable, ya que el anterior entramado de puntos de conteo de los números que son representables.