0

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)

Manumit
  • 203

1 Answers1

1

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.

Bernard
  • 175,478
  • 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.

     – Manumit Aug 30 '15 at 13:40
  • @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 – Bernard Aug 30 '15 at 14:26
  • I've got more persective now, ty. Going through it by memory will notify if something isn't right. – Manumit Aug 30 '15 at 15:04
  • 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. – Manumit Aug 30 '15 at 15:24
  • 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.$$ – Bernard Aug 30 '15 at 15:36
  • ahhh! that feeling when you finally understand. The main problem was understanding what +1 and -1 meant, but all is good now. This saves me much time, thanks again. By the way did you mean u0=0? – Manumit Aug 30 '15 at 16:10
  • Oh! One of my many typos. Yes of course, but it's too late to change the comment. – Bernard Aug 30 '15 at 16:24