Minimice$152207x-81103y$ sobre los enteros positivos.

Question

Minimizar la expresión de $152207x-81103y$ más de los enteros positivos, dado $x,y\in\mathbb{Z}.$

Así que el libro me lleva a través de la aritmética modular y cómo encontrar a $\text{gcd}(a,b)$ a fin de resolver diophantine ecuaciones. Esta pregunta aparece en el mismo capítulo.

Yo sé cómo calcular usando aritmética modular, sé cómo encontrar a $\text{gcd}(a,b)$ y resolver diophantine ecuaciones, pero no sé cómo montón de ellos juntos en el fin de resolver esto.

¿Cómo debo pensar?

Answer 1

Como $\gcd (152207,81103)=1111$ es lo mismo que el mínimo de $$1111(137x-73y)$ $

Como $137x-73y=1$ es solucionable (por ejemplo, $x=8$ y $y=15$ ) la respuesta es $1111$ .

Answer 2

Nota $c=ax+by$ ha entero solución si y sólo si $gcd(a,b)|c$ y si este existe, entonces el infinito no se entero de soluciones puede ser obtenida a partir del 1 de solución de

$x=x_{0}+\frac{b}{d}k$ e $y=y_{0}-\frac{a}{d}k$

donde $d$ es el mcd. Y $x_{0},y_{0}$ son una solución que puede ser obtenida en el algoritmo de euclides. (Como se jagy ha mencionado)

Y también el defination de $gcd(a,b)$ es de menos valor positivo de la $ax+by=d$ donde $x,y$ cualquier entero.

Answer 3

$$ \gcd( 152207, 81103 ) = ??? $$

$$ \frac{ 152207 }{ 81103 } = 1 + \frac{ 71104 }{ 81103 } $$ $$ \frac{ 81103 }{ 71104 } = 1 + \frac{ 9999 }{ 71104 } $$ $$ \frac{ 71104 }{ 9999 } = 7 + \frac{ 1111 }{ 9999 } $$ $$ \frac{ 9999 }{ 1111 } = 9 + \frac{ 0 }{ 1111 } $$ Simple continuación de la fracción de tableau:
$$ \begin{array}{cccccccccc} & & 1 & & 1 & & 7 & & 9 & \\ \frac{ 0 }{ 1 } & \frac{ 1 }{ 0 } & & \frac{ 1 }{ 1 } & & \frac{ 2 }{ 1 } & & \frac{ 15 }{ 8 } & & \frac{ 137 }{ 73 } \end{array} $$ $$ $$ $$ 137 \cdot 8 - 73 \cdot 15 = 1 $$

$$ \gcd( 152207, 81103 ) = 1111 $$
$$ 152207 \cdot 8 - 81103 \cdot 15 = 1111 $$

Answer 4

Otras personas han contestado. Pero la cosa es la idea de Bezout del Lexema (a veces conocido como la Identidad de Bezout).

Si $M,N$ son enteros con máximo común divisor $\gcd(M,N)$ entonces no existen números enteros $a,b$ , de modo que $Ma + Nb = \gcd(M,N)$.

Otra forma de poner esto es

Si $j,k$ son enteros primos relativos, entonces no existen números enteros $a,b$ , de modo que $ja + kb = 1$.

Si tenemos en cuenta que $\gcd(M,N)|M$ e $\gcd(M,N)$ entonces $\gcd(M,N)|Ma + Nb$ para cualquier enteros $a,b$ lo que conduce a una tercera forma de poner este

(Versión 3) Si $M,N$ son enteros, entonces:

1. Para cualquier enteros $a,b$ la $Ma + Nb$ será un múltiplo de $\gcd(M,N)$.

2. Enteros $c,d$ existen para que las $Mc + Nd = \gcd(M,N)$.

y por lo tanto

3. Para cualquier múltiplo de $\gcd(M,N)$, decir $k\gcd(M,N)$ para algunos entero $k$, luego enteros $a,b$ existe para que $Ma + Nb = k\gcd(M,N)$. (Solo deje $a = kc; b=kd$ donde $c,d$ son como en 2. que la anterior).

Y esto contesta a tu pregunta.

1. $152207x−81103y$ siempre será un múltiplo de $\gcd(152207, 81103) = 1111$

2. $152207x - 81103y = 1111$ va a ser posible.

Y como el menor entero positivo que es un múltiplo de a$1111$ es $1111$, el menor valor positivo de la $152207x -88103y$ es $1111$.

Aviso, no tenemos realmente para encontrar los valores que hacen de esta verdad. Es suficiente saber que se puede hacer!

====

Addendum:

1) Nota: yo no he dicho y nunca implícita de que alguno de los enteros pares eran únicos.

$Ma + Nb = k\gcd(M,N)$ tiene un infinito número de soluciones.

Aviso de $M(a \pm w\frac N{\gcd(M,N}) + N(b \mp w\frac M{\gcd(M,N)}) = Ma + Nb = k\gcd(M,N)$ que siempre habrá una solución. Pero todas las soluciones se es un formulario.

2) Para realmente encontrar una solución

$152207x -88103y =1111$ podemos usar el Algoritmo de Euclides

$152207 = 81103 + 71104; 71104 = 152207 - 81103$

$81103 = 71104 + 9999; 9999 = 81103 - 71104 = 81103 -(152207-81103) = 2*81103-152207$

$71104 = 7*9999 + 1111; 1111 = 71104 - 7*9999=(152207 - 81103)-7(2*81103-152207)=8*152207- 15*81103$

$9999 = 9*1111 + 0$ eso es lo más lejos que podamos ir.

Así, por $x = 8; y = -15$ obtenemos $152207x+81103y = \gcd(152207, 81103)$.