Mínimo de!

Question

Encuentra el mínimo de la función.

PS

dónde y $$ f(x,y)=|ax-by+c|$.

Las preguntas aquí y aquí son similares, pero son en casos en que$a,b,c \in \mathbb N$ están delimitados. Tomando las derivadas parciales, etc. no ayuda ¿Hay una manera de hacerlo de manera eficiente (para un programa de computadora)?

Answer 1

El valor positivo más pequeño que toma$ax-by$ es$\gcd(a,b)$. La búsqueda de$x_0$ y$y_0$ para la cual$ax-by$ es mínimo se puede hacer con el algoritmo de Euclides. Luego tome un múltiplo apropiado de$x_0$ y$y_0$ para acercarse lo más posible a$c$, es decir, multiplique ambos por$\tfrac{c}{\gcd(a,b)}$ redondeado al número entero más cercano.

Answer 2

Dejar $(a,b)=d$. Tenga en cuenta que para todos los$k\in \mathbb Z$, hay$x,y\in \mathbb Z$ tal que$ax-by=kd$. Además, para todos los$x,y\in \mathbb Z$,$ax-by$ tiene la forma$kd$, para algunos$k\in \mathbb Z$. Por lo tanto, el valor mínimo de$|ax-by+c|$ es el mismo que el valor mínimo de los números del formulario$|kd+c|$. Es obvio que este valor mínimo es$c$$(\mod gcd(a,b)).$