Discrete Math Understanding a proof involving the definition of divisibility

Question

In this first course on discrete mathematics, the instructor provided this following solution to a question. The question was asked us to prove the following (the solution is provided as well):

My question is where did the following expressions come from. It seems to be substitution, but I am not sure from where:

$a=2(2a+b)-(3a+2b)$

and

$b=2(3a+2b)-3(2a+b)$

Note: I have an understanding that $a|b$ can be written in the form $b=qa$, where $a,b,q$ are integers.

Edit: Please consider this is a first year course on discrete math, and I have no prior knowledge of linear algebra, etc.

Answer 1

Maybe this interpretation of the calculation will help. We know that $d$ divides $3a+2b$. Thus $$3a+2b=ds\tag{1}$$ for some integer $s$. Similarly, $$2a+b=dt\tag{2}$$ for some integer $t$. We have two equations in $a$ and $b$. Eliminate $b$ by multiplying the second equation through by $2$, and "subtracting" the first equation. We get $$a=(2)(2a+b)-(3a+2b)=2dt-ds=d(2t-s),$$ and now it is clear that $d\mid a$.

Answer 2

You want to solve the equation $a=(2a+b)x+(3a+2b)y$. Comparing coefficients of $a$ and $b$ on both sides you get $2x+3y=1$ and $x+2y=0$ (right? because the left hand side is $1\cdot a+0\cdot b$). You can then solve this system of equations simultaneously for $x$ and $y$ to get $x=2$, $y=-3$. Then do the same for the other equation $b=(2a+b)x+(3a+2b)y$ to get $x=-3$, $y=2$.

Answer 3

Sums and differences of multiples of $d$ are again multiples of $d$. So if we know that $3a+2b$ and $2a+b$ are multiples of $d$ then so is their sum $(3a+2b)+(2a+b)=5a+3b$ and their difference $(3a+2b)-(2a+b)=a+b$. Again, if $2a+b$ and - as we now know - $a+b$ are multiples of $d$, then so is their difference $(2a+b)-(a+b)=a$, and after this also the difference $(a+b)-a=b$.

More systematically, any combination $u(3a+2b)+v(2a+b)$ with integers $u,v$ is a multiple of $d$. As $u(3a+2b)+v(2a+b)=(3u+2v)a+(2u+v)b$ and we want to have only $a$, we should look at the case where the coefficient before $b$ is zero, i.e., $2u+v=0$ or $v=-2u$. Substituting this into the coefficient of $a$, we find $(3u+2(-2u))a=-ua$; hence by letting $u=-1$ (and then $v=2$), we find that $a$ is a multiple of $d$.

Answer 4

It's not substitution. It's just an identity:

$a = 4a - 3a$

$= 4a - 3a + 2b - 2b$

$= (4a + 2b) - (3a + 2b)$

$= 2(2a + b) - (3a + 2b)$.

and $b = 2(3a + 2b) - 3(2a - b)$ is don't similarly.

Then they used substitution.

A natural question to ask would be how in heck could they just stumble on the right manipulation that would work.

Well, what we could have done when we had $3a + 2b = sd$ and $2a + b = td$ we could have tried to solve directly for $a$ and $b$. It's basic two equations, two unknowns.

$3a + 2b = sd$

$2a + b = td$

$4a + 2b = 2td$

$(4a + 2b) - (3a + 2b) = 2td - sd$

$a = d(2t-s)$

====

$6a + 4b = 2sd$

$6a + 3b = 3td$

$(6a + 4b) - (6a + 3b) = 2sd - 3td$

$b = d(2s - 3t)$

And from that they probably worked backwards. Although to be honest I'm not sure why. Solving directly is just as illuminating and takes out the "well, that was lucky!" factor.

=====

Actually I'd have done this a lot more straightforwardly.

Lemma: $d|n$ and $d|m$ then $d|n \pm m$ or more generally $d|kn + lm$ for all $k,l$.

Proof:$d|n \implies n = sd$ and $d|m \implies m = td$ for some $s,t$. Then $n \pm m = sd \pm td = d(s \pm t)$ so $d|n \pm m$. Likewise $kn + lm = ksd + ltd = d(ks + lt)$ so $d|kn + lm$.

Then... we just do it:

$d|3a + 2b$ and $d|2a + b$ so $d|(3a + 2b)-(2a+b)$ so $d|a + b$ so $d|(2a + b) - (a+b)$ so $d|a$ so $d|(a+b) - a$ so $d|b$.