MAT102 Lecture 8

• 2
  • a
    • Show that the equation $ax+by=c$ only has a solution if $gcd(a,b)\mid c$
    • $d=gcd(a,b)$
    • $d\mid c$
    • Divisibility means multiple of a number.
    • So $c$ is a multiple of $d$.
    • $c=dk$ for some $k\in Z$.
    • If we have $gcd(a,b)$ then:
      • $a=d{k}_1$
      • $b=d{k}_2$
      • Where the $d=gcd(a,b)$
      • $a$ and $b$ are multiples of a common divisor $d$.
    • Substitute it back into our equation.
    • $(d{k}_1)x+(d{k}_2)y=c$
    • Now we will prove that the above can turn into $c=dk$ for some $k\in \mathbb{Z}$. This will prove that $gcd(a,b)\mid c$ because $c=dk$ is the same as $d\mid c$
    • $d{k}_{1}x+d{k}_{2}y=c$
    • $d(k_{1}x+k_{2}y)=c$
      • $k_{1}x+k_{2}y=k$
    • $dk=c$
    • Thus $d\mid c$ or $gcd(a,b)\mid c$.
    • With bézout's identity, we know that if we have two integers, then there are other integers that add up to the GCD.
    • $a{x}_0+b{y}_0=gcd(a,b)$
    • $a{x}_0+b{y}_0=d$
    • We know what $dk$ is so we can modify this equation to become $dk$.
    • $k(a{x}_0+b{y}_0)=dk$
    • $ka{x}_0+kb{y}_0=dk$
    • Since $c=dk$ then we can replace this to find our $c$ value.
    • $ka{x}_0+kb{y}_0=c$
    • let $x=k{x}_0$ and $y=k{y}_0$
    • $ax+by=c$
    • So then there are solutions if the $gcd(a,b)\mid c$.

    ---

    • $⟹$
      • Assume $\mathrm{\exists }m,n\in \mathbb{Z}$ such that $am+bn=c$.
        • Assume a solution
      • We know that the $gcd(a,b)\mid a$ and $gcd(a,b)\mid b$
        • if you divide a and b, you divide any linear combination.
      • $gcd(a,b)\mid (am+bn)=c$
        • Here $m,n$ are just two integers.
    • $⟺$
      • Supped $gcd(a,b)\mid c$ such that $\mathrm{\exists }k\in \mathbb{Z}$.
      • $gcd(a,b)k=c$
      • By bézout. $\mathrm{\exists }m,n\in \mathbb{Z}$ such that $(am+bn)=gcd(a,b)$.
      • Multiply by k
      • $a(mk)+b(nk)=gcd(a,b)k=c$
  • b
    • Assume $d>0$
    • $⟹$
      • If $a,b,c\in \mathbb{Z}$ and $d\ne 0$. Show that $gcd(ad,bd)=dgcd(a,b)$.
      • By bézout $\mathrm{\exists }m,n\in \mathbb{Z}$ such that $am+bn=gcd(a,b)$
      • Multiply by d
      • $ad(m)+bd(n)=dgcd(a,b)$
      • So $gcd(ad,bd)\mid dgcd(a,b)$
    • $⟺$
      • By bézout
      • $\mathrm{\exists }m,n\in \mathbb{Z}$
      • $adm+bdn=gcd(ad,bd)$
      • Divide by d
      • $am+bn=\frac{gcd(ad,bd)}{d}$
      • The right is still an $\mathbb{Z}$.
      • By part (A), the $gcd(a,b)\mid \frac{gcd(ad,bd)}{d}$
      • $dgcd(a,b)\mid gcd(ad,bd)$