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.
$\endgroup$ 74 Answers
$\begingroup$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$.
$\endgroup$ $\begingroup$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$.
$\endgroup$ $\begingroup$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$.
$\endgroup$ $\begingroup$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$.
$\endgroup$
