Número de soluciones pares de $ax+by=n$

Question

Pregunta: Dado que $a, b, n$ son enteros positivos y $x, y$ son enteros no negativos tales que $$ax+by=n$$ tiene al menos un par de soluciones $(x, y) $ . Cuántos pares de soluciones $(x, y) $ ¿están ahí?

Por ejemplo, $$2x+3y=12$$ tiene $3$ pares de soluciones. Son $$(3,2),(6,0), (0,4).$$ Sin embargo, no tengo ni idea de cómo encontrar una fórmula general.

Answer 1

Dejemos que $ (x_0,y_0) $ sea una solución de $ ax+by = n $ , entonces por alguna teoría elemental de números, toda la solución de enteros está dada por $$ x=x_0+\frac{b}{(a,b)}t,y = y_0-\frac{a}{(a,b)}t $$ donde $ (a,b) $ es el máximo común divisor y $ t $ es un número entero cualquiera. Por lo tanto, basta con dejar que $$ -\frac{(a,b)x_0}{b}\leq t\leq \frac{(a,b)y_0}{a}. $$ Porque $ -\frac{(a,b)x_0}{b} $ y $ \frac{(a,b)y_0}{a} $ pueden no ser enteros, no existe una fórmula analítica.

Pero el número de soluciones es aproximadamente $\frac{n(a,b)}{ab}$ porque $\frac{x_0}{b}+\frac{y_0}{a}=\frac{n}{ab}$ .

Answer 2

Si GCD od $a$ y $b$ es 1. Sean los pares de enteros $(x_0,y_0)$ sea la primera solución de $ax+by=n~(*)$ . Entonces Sea $x=x_0+bm, y=y_0-am$ son las posibles soluciones. Dado que ambos $x,y \ge 0$ puede encontrar fácilmente los posibles valores de $m$ y, por tanto, el número de soluciones. El número de soluciones de esta Ec (*). son $N=[\frac{n}{ab}]$ donde $[.]$ significa parte entera. También, $N$ puede ser uno más que éste si el resto( $r$ ) cuando $n$ se divide por $ab$ satisface la relación $ax+by=r$ un par de enteros no negativos $x$ y $y$ .

Answer 3

Teorema

Supongamos que la ecuación de la diofanitina $ax+by=c$ tiene solución $\{x_0,y_0\}\subset\mathbb{Z}$

$$\text{And } d:=\gcd(a,b)\mid c$$

$$\text{Then }\forall m\in\mathbb{Z},s.t.\{x_0+m\cdot\frac{b}{d},y_0-m\cdot\frac{a}{d}\}\subset\mathbb{Z}\text{ are all the solutions}$$

Prueba.

Por la suposición de que $\{x_0,y_0\}$ es una solución ya que

$$a(x_0+m\frac{b}{d})+b(y_0-m\frac{a}{d})$$

$$=ax_0+m\frac{ab}{d}+by_0-m\frac{ab}{d}$$

$$=ax_0+by_0=c$$

Esto demostró que sí son soluciones para $ax+by=c$

Y el resto es sólo para demostrar que son las únicas soluciones $\dots$

Esta prueba se puede encontrar en

"UTM-Una introducción legible a las matemáticas reales-Capítulo $7$ -Teorema $7.2.10$ ."