Divisibility

• If $a,b\in \mathbb{N}$, we say that $a$ divides $b$, and denote $a|b$, if $\exists c\in \mathbb{N}:a\cdot c=b$

  • Other terms: $a$ divides $b$, $a$ is a divisor of $b$ , $a$ is a factor of $b$, $b$ is a multiple of $a$, and $b$ is divisible by $a$
  • Properties
    • Reflexivity - $\forall a\in \mathbb{N},a|a$
    • $\forall a\in \mathbb{N},1|a$
    • $\forall a,b\in \mathbb{N},(a|b⟺a\le b)$
    • Antisymmetry - $a|b\wedge b|a⟺a=b$
    • Transitivity - $a|b\wedge b|c⟹a|c$
    • $c\mid a\wedge c\mid b⟹c\mid (ma+nb)$

• $a\nmid b$ if $a$ does not divide $b$