It is clear that 253x + 256y = 253(x+y) + 3y. For a pair of integers x and y satisfying: $$253x + 256y = 1$$
The absolute value of x is minimum. Then, x = ? and y = ?
I tried squaring the equation to make it a quadratic, and seeing if I can make a graph of it from there, but that didn't work as my variables always cancelled out. I thought about trying to do a calculus maximization/minimization but I have no idea on how to even start when all I'm given is two of the exact same equation.
All help is appreciated! The answers are x = 85 and y = -84
This is the Extended Euclidean Algorithm. I don't much like the "back-substitution" step, I prefer to get the desired Bezout identity through continued fractions. The last line below says $ 256 \cdot 84 - 253 \cdot 85 = -1 .$ This confirms that the two numbers are coprime. In turn this says that all such relations can be expressed as
$ 256 \cdot (84 + 253 t) - 253 \cdot (85 + 256t) = -1 .$ You want $+1$ so
$$ -256 \cdot (84 + 253 t) + 253 \cdot (85 + 256t) = 1 .$$ Then we see $x = 85 + 256 t.$ The values of $x$ with modest absolute value are $t=-2, t=-1, t=0, t=1$ or $x= -427, -171, 85, 341$ so that the minimum absolute value is $x=85. \; $ This happens when $t=0$ so the coefficient of $256$ is $y=-84$
$$ \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc $$
$$ \gcd( 256, 253 ) = ??? $$
$$ \frac{ 256 }{ 253 } = 1 + \frac{ 3 }{ 253 } $$ $$ \frac{ 253 }{ 3 } = 84 + \frac{ 1 }{ 3 } $$ $$ \frac{ 3 }{ 1 } = 3 + \frac{ 0 }{ 1 } $$ Simple continued fraction tableau:
$$ \begin{array}{cccccccc} & & 1 & & 84 & & 3 & \\ \frac{ 0 }{ 1 } & \frac{ 1 }{ 0 } & & \frac{ 1 }{ 1 } & & \frac{ 85 }{ 84 } & & \frac{ 256 }{ 253 } \end{array} $$ $$ $$ $$ 256 \cdot 84 - 253 \cdot 85 = -1 $$