Find integers $\alpha$ and $\beta$ such that $37469\alpha+52464\beta=-11$

Question

Find integers $\alpha$ and $\beta$ such that $37469\alpha+52464\beta=-11$

(hint: First find $a$ and $b$ such that $37469a+52464b=\gcd(37469,52464).$

I want to make sure I did the steps correctly ; but i'm getting stuck here since the gcd $1,$ but the real question is asking us to equal to $-11.$

Okay following the comments, I got $a= -31195$ and $b= 22279$ when equaling to $\gcd 1$, now multiplying $a$ and $b$ by $(-11)$ I get that $a=343145$ and b=$-245069$ which does end up getting $-11.$ So my true $\alpha = 343145$ and $\beta= -245069$?

Answer 1

"but i'm getting stuck here since the gcd 1, but the real question is asking us to equal to -11"

Not a problem.

If $Ka + Jb = 1$ then let $\alpha = -11a; \beta = -11b$ and then $K\alpha + J\beta = -11$.

Of course those might not be the closest and "nicest" answers.

We can also let $\alpha = -11a + mJ$ and $\beta = -11b - mK$ where $m$ is any integer then $K\alpha + J\beta = -11Ka + mJK - 11Jb - mJK = -11(Ka + Jb) = -11$.

This way we can get numbers close together.

===

Example:

$52464 - 37469 = 14995$

$37469 - 2*14995=7479$

$14995 - 2*7479=37$

$7479 - 202*37 =5$

$37 - 7*5 = 2$

$5 - 2*2 = 1$

$(7479 - 202*37) - 2(37 - 7*5)=1$

$7479 - 204*37 + 14*5 = 1$

$7479 - 204*37 + 14*(7479 - 202*37) = 1$

$15*7479 - 3032*37 = 1$

$15*7479 - 3032*(14995 - 2*7479) = 1$

$6079*7479 - 3032*14995 = 1$

$6079*(37469 - 2*14995) - 3032*14995 = 1$

$6079*37469-15190*14995 = 1$

$6079*37469-15190*(52464 - 37469) = 1$

$21269*37469 - 15190*52464=1$

So $a = 21269$ and $b = -15190$ and

$\alpha = -11*37469 = -233959; \beta = -11*-15190=167090$ gives us

$-233959*37469 + 167090*52464 = -11$

However $-233959$ and $167090$ are very far apart (which is not a problem).

But if $\alpha = -233959 +6*52464 = 80825$ and $\beta = 167090 - 6*37469 = -57724$

we get your answer.

(Which aren't the absolute closest but ... who cares).

Answer 2

If you use (extended) Euclidean algorithm and find $a$ and $b$ such that $37469a+52464b=1$, you can multiply it by $-11$ to get $37469(-11a)+52464(-11b)=-11$. Thus, $\alpha = -11a$ and $\beta = -11b$ are the solutions you are looking for.