So I am currently trying to prove some basic divisibility relations, as follows.

  • If $a \mid b$ and $a \mid c$, then $a \mid b + c$.
  • If $a \mid b$ and $s \in \mathbb{Z}$, then $a \mid sb$.
  • If $a \mid b$ and $a \mid c$ and $s$, $t \in \mathbb{Z}$, then $a \mid sb + tc$.
  • If $a \mid b$ and $b \mid c$, then $a \mid c$.
  • $a \mid 0$ for all $a \neq 0$.
  • $1 \mid b$ for all $b \in \mathbb{Z}$.
  • If $a \mid b$ and $b \neq 0$, then $|a| \le |b|$.
  • If $a \mid b$, then $\pm a \mid \pm b$.

I frequently find myself having trouble showing these quite basic facts.

  1. What should I keep in mind when trying to prove these properties, i.e. what techniques are useful?
  2. What is the intuition for the proofs of these facts, or rather, morally why must these facts be true?

Thanks in advance.

  • 7
    $\begingroup$ The proofs are often easy consequences of the definition of divisibility. We have $a\mid b$ if there is a $k$ such that $b=ka$. $\endgroup$ – André Nicolas Jul 6 '16 at 20:19
  • $\begingroup$ Example: for the first one, write $b = ak$ and $c=ad$. Then $b+c = ak + ad = a(k+d)$. $\endgroup$ – MathematicsStudent1122 Jul 6 '16 at 20:30
  • $\begingroup$ Most of the divisibility properties are translations of the fact that $\,\Bbb Z\,$ is a subring of $\,\Bbb Q,\,$ which is clear if you reformulate them in fractional form. This viewpoint lends some further intuition (and leads to generalized divisibility relations). See this answer for further discussion. $\endgroup$ – Bill Dubuque Jul 11 '16 at 0:43
  • $\begingroup$ Besides the third one (which is derived from the first two), all of those should be intuitively obvious as long as you really understand what $a\mid b$ means. If anything, these are the sorts of facts that should be built into your intuition after experience, not built from intuition (although it is easy to confuse the two after familiarity). But many of those items can be reinterpreted in light of modular arithmetic and order theory. (One last note, even $0\mid 0$ is true, so the stipulation that $a\ne 0$ in the claim $a\mid 0$ is unnecessary, at least with my definitions.) $\endgroup$ – arctic tern Jul 15 '16 at 7:31

Good question.

It may be easiest to prove some of these facts straight from the definition. That is, recall that $a|b\implies \exists k\in\mathbb{Z}$ such that $ak=b$. For your first property, we have $ak=b$ and $al=c$ for some $k,l\in\mathbb{Z}$.

When we add those two together we find $ak+al=b+c$. Then, by distributivity, $(k+l)a=b+c$. Since $k+l\in\mathbb{Z}$, we have that $a|(b+c)$ by definition.

Hopefully that provides some framework to prove some of these other statements since many amount to simple algebraic manipulation once you apply the definition of "divides."

  • $\begingroup$ @user26857 I think I was just overexcited to answer a question. "Great" has been changed to "Good." $\endgroup$ – user322548 Dec 6 '16 at 22:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy