MAT102 Tutorial W6B

• 1
  • a
    • $\begin{array}{cc}116& =48(2)+20\\ 48& =20(2)+8\\ 20& =8(2)+4\\ 8& =4(2)+0\end{array}$
    • $gcd(116,48)=4$
  • b
    • find the solution for: $232x+96y=8$
    • $\begin{array}{cc}232& =96(2)+40\\ 96& =40(2)+16\\ 40& =16(2)+8\\ 16& =8(2)\end{array}$
    • You can also do $232x+96y=8⟹29x+12y=1$
    • $(96+40(-2))+(40+(16)(-2))(-1)=8$
    • $96+40(-2)+40(-1)+16(2)=8$
    • $96+40(-3)+16(2)=8$
    • $96+(232+96(-2))(-3)+(96+40(-2))(2)=8$
    • $96+232(-3)+96(6)+96(2)+40(-4)=8$
    • $96(1)+232(-3)+96(6)+96(2)+40(-4)=8$
    • $96(9)+232(-3)+40(-4)=8$
    • $96(9)+232(-3)+(232+96(-2))(-4)=8$
    • $96(9)+232(-3)+232(-4)+96(8)=8$
    • $96(17)+232(-7)=8$
    • Do it with the $29x+12y=1$ equation you get $x=5,y=-12$
• 2
  • a - If $gcd(a,b)\nmid c$, then $ax+by=c$ has no integer solutions
    • By the euclidean algorithm, see that we have that the $gcd(a,b)$ exists, and it's not $1$. So they're not coprime.
    • $ax+by=c$ will have solutions by the previous example since we know that $ax+by=gcd(a,b)$.
    • So any multiple of $c$ where $gcd(a,b)\mid c⟹c=kgcd(a,b)$ will have solutions too.
    • If $gcd(a,b)\nmid c$, then we have no solutions since there is no multiple of $gcd(a,b)$ where the equation has solutions.
    • Proof:
      • If we have $a,b,c\in \mathbb{Z}$
      • With $d=gcd(a,b)$
      • We have a linear diophantine equation $ax+by=c$
      • $⟹$
        • If there are $x,y$ where $ax+by=c$. Then we have $d\mid a$ and $d\mid b$ so $d$ divides any
    • Solution:
      • Contradiction
      • $d=gcd(a,b)\in \mathbb{Z}$
      • $a=dm$ for $m\in \mathbb{Z}$
      • $b=dn$ for $n\in \mathbb{Z}$
      • Assume that $ax+by=c$ has an integer solution. ($x,y\in \mathbb{Z}$)
      • this means that $a,b$ can be rewritten as multiples of $x,y$
      • $⟹$
        • $dmx+dny=c$
        • $d(mx+ny)=c$
        • See that $x,y,m,n\in \mathbb{Z}$
        • This means that $dk=c$ for $k=mx+ny\in \mathbb{Z}$
        • This is a contradiction, we assumed that $d\nmid c$
  • b
    • Does $6x+12y=5$ have integer solutions?
    • $gcd(6,12)=6$
    • $6\nmid 5$, so there are no solutions