Diophantine Equation - least values for n : absolute values

Question

Find all solutions to the diophantine equation

$323x + 278y = 7$

Choose also a solution for which $|x| + |y|$ is as small as possible.

My approach to this is to do the usual euclidean algorithm

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

Then i do the extended euclidean algorithm to drive it back up

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

The particular solution is $x_0 = -735, \quad y_0 = 854$

and the particular solution is $x = -735 + 278n, \quad y = 854 - 323n$

Upto this point, we're all good. But the problem is choosing the least value of n that produces $|x| + |y|$.

My approach to this has always been to try out different values of n until i find the answer. It takes quite a lot of time but i think out there, theres gotta be some sort of a quick method to the most suitable value of n

Answer 1

Yes you started correctly.

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

You can quickly minimize $\mid x \mid$ by choosing $n \approx \frac{735}{278}$ so either $n=2,3$ will be best. For $2$ you get $-179$ and for $3$ you get $99$.

Now do $\mid y \mid$. $n \approx \frac{854}{323}$ so either $n=2,3$ will be best. For $2$ you get $208$ and for $3$ you get $-115$.

$n=3$ minimizes both individually so it will minimize the sum $\mid x \mid + \mid y \mid$. There is no conflict between minimizing the summands individually. This is a lucky case.

Answer 2

For example for $x(n)=359100+139n \space $ and $y(n)=-976500-378n$ we have 2 cases, to the function $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 $$

So we want to minimize g (same function as f), choosing the best value of n. There could have been 3 cases, but because both x and y change sign for the same n there is no intermediate case. See how the value of g(n) changes when n changes to either side from the intersection, it always grows. So we conclude that the best value of n must be $-2584$ or $-2583$. Evaluating: $$g(-2583)=189$$ $$g(-2584)=328$$

Therefore, the best n is $n=-2583$