Ecuación diofántica - menos valores para n: valores absolutos

Question

Encuentre todas las soluciones de la ecuación de diophantine

$323x + 278y = 7$

Elige también una solución para que $|x| + |y|$ es tan pequeño como sea posible.

Mi enfoque es hacer el habitual algoritmo de euclides

$278 = 0*323 + 278 \quad ... \quad 2 = 2*1 + 0$

Luego hago el algoritmo de euclides extendido a la unidad de copia de seguridad

$1 = (1 * 3) + (-1 * 2) \quad ... \quad 1 = (122 * 278) + (-105 * 323)$

La solución particular es $x_0 = -735, \quad y_0 = 854$

y la solución particular es $x = -735 + 278n, \quad y = 854 - 323n$

Hasta este punto, todos estamos bien. Pero el problema es elegir el menor valor de n que produce $|x| + |y|$.

Mi acercamiento a este siempre ha sido para probar diferentes valores de n hasta encontrar la respuesta. Lleva un montón de tiempo, pero creo que por ahí, hay que ser algún tipo de un método rápido para la mayoría de adecuado valor de n

Answer 1

Sí se ha iniciado correctamente.

$$ x = a 735+278n\\ y=854−323n\\ $$

Usted puede minimizar rápidamente $\mid x \mid$ eligiendo $n \approx \frac{735}{278}$ por lo tanto $n=2,3$ va a ser mejor. Para $2$ obtener $-179$ e de $3$ obtener $99$.

Ahora lo $\mid y \mid$. $n \approx \frac{854}{323}$ por lo tanto $n=2,3$ va a ser mejor. Para $2$ obtener $208$ e de $3$ obtener $-115$.

$n=3$ minimiza tanto de forma individual, de manera que se minimice la suma de $\mid x \mid + \mid y \mid$. No hay ningún conflicto entre la minimización de los sumandos de manera individual. Este es un caso afortunado.

Answer 2

Por ejemplo, para $x(n)=359100+139n \space $ e $y(n)=-976500-378n$ tenemos 2 casos, a la función de $f(x,y)=|x|+|y|$: $$g(n)=f(x,y)=-x+y=-1335600-517n, \space n \leq -2584 $$ $$g(n)=f(x,y)=x-y=1335600+517n, \space n \geq -2583 $$

Así que queremos minimizar la g (la misma función como f), elegir el mejor valor de n. Podría haber habido 3 casos, pero debido a que ambos x e y cambio de signo para el mismo n no hay ningún caso intermedio. Ver cómo el valor de g(n) cambios cuando n cambios a cada lado de la intersección, siempre crece. Así llegamos a la conclusión de que el mejor valor de n debe ser $-2584$ o $-2583$. La evaluación de: $$g(-2583)=189$$ $$g(-2584)=328$$

Por lo tanto, la mejor n es $n=-2583$