Demostrar para números relativamente primos.

Question

Demostrar que para números enteros positivos relativamente primos $a$ y $b$ la ecuación $ax+by=c$ debe tener una solución entera no negativa si $c>ab-a-b$ .

Answer 1

Esquema: La ecuación tiene solución $(x_0,y_0)$ en enteros uno de los cuales puede ser negativo.

Todas las soluciones tienen forma $x=x_0-bt$ , $y=y_0+at$ , donde $t$ se extiende sobre el enteros .

Elija $t$ para que $x_0-bt$ es no negativo y lo más pequeño posible. Entonces $0\le x_0-bt\lt b$ . Así, $x_0-bt\le b-1$ y $$b(y_0+at)=c-a(x_0-bt)\gt ab-a-b-a(b-1)=-b.$$ Desde $b(y_0+at)\gt -b$ Debemos tener $y_0+at\ge 0$ . Así que hemos encontrado $t$ de manera que ambos $x_0-bt$ y $y_0+at$ son no negativos.