0
$\begingroup$

I want to learn how solve simple ax+by=c with matrices (assuming that's the fasted method?),
but it's difficult to find correct learning material.

I've been through this process:

4386x + 89744y = 2

enter image description here

NB: Matrices are unknown terrotorium, go easy, ty.
(links are also appreciated)

$\endgroup$
1
$\begingroup$

You don't need matrices really, only use the Extended Euclidean algorithm. Here is a layout for it. I continued one line further, in order to obtain the quotient of the two given numbers by their gcd: enter image description here

Thus you have a solution: $\;(x,y)=(-22\,303,1090)$. The theory tells us all other solutions have the form: $$(x,y)=\Bigl(-22\,303+k44\,872,1090-k2193),\quad k\in\mathbf Z.$$

Some explanations:

Not only the gcd is a linear combination of the two given numbers, but all intermediate remainders (easy induction). Si if $r_i+1$ denotes the remainder and $q_i$ the quotient in the $i$-th division (initialisation for the remainders: $r_0=89\,744$, $r_1=4386$), we have $$r_{i-1}=q_ir_i+r_{i+1}\iff r_{i+1}=r_{i-1}-q_ir_i,$$ and of course the same relation is valid for the coefficients $u_i,v_i$, by linearity.

$\endgroup$
  • $\begingroup$ My god, it's beautiful. The level of compactness! Can you please explain the whole formula with words? And then some questions 1. Why isn't "Ui" called x? Why isn't "Vi" called y? Why isn't "Ri" called gcd? I also have several questions about the formula but I'll wait untill you explain it with words. $\endgroup$ – Manumit Aug 30 '15 at 13:40
  • $\begingroup$ @Manumit: I've added some explanations. Is that clearer? For the notations of the coefficients, I took these from a context where there was no unknown, they were the traditional notations I learnt. The index is necessary, since there is a whole sequence of $x$s and $y$s to compute recursively $\endgroup$ – Bernard Aug 30 '15 at 14:26
  • $\begingroup$ I've got more persective now, ty. Going through it by memory will notify if something isn't right. $\endgroup$ – Manumit Aug 30 '15 at 15:04
  • $\begingroup$ Ok, I can't figure out how you calculate Ui and Vi, most of your numbers aren't written down anywhere in my answer. explain e.g. how you got -20 in Ui and 11 in Vi. Thanks for patience, I'm still at highschool level in math. $\endgroup$ – Manumit Aug 30 '15 at 15:24
  • $\begingroup$ They're initialised with $u_0=1, u_1=1$ and $v_0=1, v_1=0$ for obvious reasons. The general relation come from the analogous relations between $r_{i+1}, r_i$ and $r_{i-1}$ (which you wrote in your own post): $$u_{i+1}=u_{i-1}-q_iu_i,$$ $$v_{i+1}=v_{i-1}-q_iv_i.$$ $\endgroup$ – Bernard Aug 30 '15 at 15:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.