MAT102 Lecture 15B

• We say that a divides b ($a\mid b$) if $ak=b,k\in \mathbb{Z}$
• Think about it these ways
  • b is a multiple of a
  • a is a factor of b
• Suppose that $a\mid b$ and $a\mid c$, does $a\mid (b+c)$
  • $ak=b$
  • $a\ell =c$
  • $ai=b+c$
  • $ai=ak+a\ell$
  • See you can take a factor out
  • $i=k+\ell$
  • $b+c=ak+a\ell$
  • $b+c=a(k+\ell )$
  • So $a\mid b+c$
• If $a\mid b$ and $a\mid c$, then $a\mid (bm+cn)$ for all $m,n\in \mathbb{Z}$
  • It will divide any linear combination
• Exercise:
  • If $a\mid bc$ and $gcd(a,b)=1$ then $a\mid c$
  • $ak=bc,k\in \mathbb{Z}$
  • Think about it like factoring:
    • $2\cdot 3\mid 3\cdot 4$
    • See that we can pull out factor of $3$ and $2$
  • Proof:
    • $ak=bc,k\in \mathbb{Z}$
    • $gcd(a,b)=1$
      • $ax+by=1$
    • Want to show that $a\mid c⟹a\ell =c$
    • $a{x}_0+b{y}_0=1$ has these solutions $(x_0,y_0)$
  • Solution:
    • Rough Work:
      • $ak=bc$
      • $a{x}_0+b{y}_0=1$
      • $gcd(a,b)\mid a$
      • $gcd(a,b)\mid b$
      • Multiply by $k$
        • $ka{x}_0+kb{y}_0=k$
        • $bc{x}_0+kb{y}_0=k$
        • $b(x_0+k{y}_0)=k$
      • Multiply by $c$
        • $ca{x}_0+cb{y}_0=c$
        • $ca{x}_0+ak{y}_0=c$
        • $a(c{x}_0+k{y}_0)=c$
        • Proven
    • Solution:
      • Suppose $a\mid bc$ and $gcd(a,b)=1$
      • We know that $ak=bc,k\in \mathbb{Z}$
      • If $gcd(a,b)=1⟹a{x}_0+b{y}_0=1$ by Bézout
      • Multiply by $c$
      • $ca{x}_0+bc{y}_0=c$
      • Sub in $ak=bc$
      • $ca{x}_0+ak{y}_0=c$
      • Factor out $a$
      • $a(c{x}_0+k{y}_0)=c$
      • So $a\mid c$ as required
• 4
  • $b\mid a^2$
    • $bk=a^2$
  • $b\mid a$
    • $b\ell =a$
  • $p$ is prime $⟺$ whenever $p\mid ab$ then $p\mid a$ or $p\mid b$
  • $⟹$
    • Suppose $p$ is prime and $p\mid ab$
    • Let's show that $p\mid a$ or $p\mid b$
    • Without loss of generality
    • If $p\mid a$ we're done
    • Suppose $p\nmid a$
      • Let's show that $p\mid b$
        • $pk=b$
      • If $p\nmid a$ then $gcd(p,a)=1$
      • So $p{x}_0+a{y}_0=1$
      • So then $p\mid b$ by the exercise above
  • $⟸$
    • #tk