Soluciones a la ecuación lineal diofantina $15x+21y=261$

Question

Pregunta

¿Cuántas soluciones positivas hay para $15x+21y=261$ ?

Lo que tengo hasta ahora
$\gcd(15,21) = 3$ y $3|261$
Así que podemos dividir por el gcd y obtener:
$5x+7y=87$

Y no sé muy bien hacia dónde ir a partir de este punto. En particular, necesito saber cómo saber cuántas soluciones hay.

Answer 1

Como ha observado, podemos reducir al caso en que $a$ y $b$ son relativamente primos. Dado que es relativamente primo positivo enteros $a$ y $b$ y un positivo $c$ queremos encontrar el número de soluciones de $ax+by=c$ en números enteros positivos $x$ , $y$ .

Daremos un exactamente respuesta, y una mucho más sencilla de calcular aproximado respuesta que podría estar fuera de lugar por $1$ . El argumento que lleva a estas respuestas se da a continuación. Las respuestas en sí vienen después del argumento.

---

Hay enteros $x_0,y_0$ , de tal manera que $ax_0+by_0=c$ . Una solución $(x_0,y_0)$ se puede encontrar utilizando el Algoritmo euclidiano ampliado para resolver la ecuación $au+bv=1$ y multiplicando por $c$ . Los detalles se pueden encontrar en muchos lugares. Nosotros, en cambio, nos centraremos en las consecuencias. Obsérvese que el $x_0$ y $y_0$ encontradas a través de este proceso no serán ambas positivas.

Una vez que hayamos encontrado una solución $(x_0,y_0)$ todas las soluciones enteras de la ecuación $ax+by=c$ tienen la forma $x=x_0+bt$ , $y=y_0-at$ , donde $t$ se extiende sobre los números enteros. Para producir las soluciones positivas, queremos encontrar todos los enteros $t$ tal que $x>0$ y $y>0$ .

Así que necesitamos $y_0-at >0$ , $x_0+bt>0$ o, por el contrario $$-\frac{x_0}{b}<t <\frac{y_0}{a}.$$

---

Respuesta exacta: El número de soluciones positivas $(x,y)$ es el número de enteros $t$ en el intervalo $-x_0/b<t <y_0/a$ . Esto es fácil de determinar una vez que sabemos $x_0$ y $y_0$ .

Respuesta aproximada: El intervalo $(-x_0/b,y_0/a)$ tiene una anchura $y_0/a+x_0/b$ . que se simplifica a $(ax_0+by_0)/ab$ Es decir, $c/ab$ .

Si $\dfrac{c}{ab}$ es un entero, entonces la anchura de nuestro intervalo abierto es un entero, y el número de enteros en el intervalo es $\dfrac{c}{ab}-1$ . Si $\dfrac{c}{ab}$ no es un entero, entonces el número de enteros en nuestro intervalo abierto puede ser $$\left\lfloor \dfrac{c}{ab}\right\rfloor \qquad \text{or}\qquad \left\lfloor \dfrac{c}{ab}\right\rfloor+ 1.$$

Para un ejemplo sencillo que demuestre que $c/ab$ no es necesario bastante Determinar el número de soluciones positivas, observar que $x+15y=23$ tiene una solución positiva, mientras que $3x+5y=23$ tiene dos soluciones positivas.

Si damos la respuesta $c/ab-1$ si $c/ab$ es un número entero, y $\lfloor c/ab\rfloor$ de lo contrario, tenemos la garantía de que estamos subestimando la verdadera respuesta en un máximo de $1$ .

La ventaja es que la respuesta aproximada puede encontrarse de forma muy económica. En nuestra respuesta exacta, utilizamos $x_0$ y $y_0$ por lo que habría que calcularlos.

Answer 2

Aplicar el Algoritmo de Euclides-Wallis , $$ \begin{array}{r} &&1&2&2\\ \hline\\ 1&0&1&-2&5\\ 0&1&-1&3&-7\\ 21&15&6&3&0 \end{array} $$ La penúltima columna dice que $3\cdot15+(-2)\cdot21=3$ multiplicando esto por $87$ , produce $261\cdot15+(-174)\cdot21=261$ . La última columna dice que la solución general es $(261-7k)\cdot15+(-174+5k)\cdot21=261$ . Utilizando $k=35,36,37$ obtenemos el $3$ soluciones no negativas: $$ \begin{align} 16\cdot15+1\cdot21&=261\\ 9\cdot15+6\cdot21&=261\\ 2\cdot15+11\cdot21&=261\\ \end{align} $$

Answer 3

5, 7 y 87 son números lo suficientemente pequeños como para poder probar todas las posibilidades. ¿Puedes ver, por ejemplo, que $y$ no puede ser mayor de 12?

Answer 4

encontrará todas las soluciones de $ax+by=c$ con

$$x=x_0-\frac{b}{(a,b)}*t , y=y_0+\frac{a}{(a,b)}*t$$

$x_0$ y $y_0$ que encuentras con el algoritmo euclidiano hacia atrás:

$15x+21y=261$ con $261=3*87$

21=1*16+6

15=2*6+3

6=2*3+0

$3=15-2*6=15-2*(21-1*15)=15-2*21+2*15=3*15-2*21$

multiplicado por 87 obtenemos

$261=261*15-174*21$

Así que $x_0=261$ y $y_0=174$

Answer 5

Sugerencia $\ $ Es fácil. $\rm\:x\ge 1\:\Rightarrow\: y = (87-5x)/7 \le \lfloor 82/7\rfloor = 11.\:$ Cada uno de los intervalos $[1,5], [6,10]$ contiene precisamente una solución para $\rm\:y,\:$ por lo que queda por comprobar si $\rm\:y=11\:$ da una solución.

Obsérvese que el algoritmo euclidiano (ampliado) es no necesario, y este método funciona en general.