Theorem (Properties if Division)
Let
$a, \; b$
be positive integers, and let
$c, \; d$
be any integers. Then
a) If
$a | c$
then
$a | (c+na)$
for any integer
$n$
.
b) If
$c \neq 0$
and
$a | c$
then
$a \le |c|$
.
c) If
$a | b$
and
$b | a$
then
$a=b$
.
d) If
$a | b, \; b | c$
then
$a | c$
.
e) If
$a | c, \; a | d$
then
$a | (mc+nd)$
for any integers
$m, \; n$
.
Proof
a)
$a |c$
so there is an integer
$q$
such that
$aq=c$
. Then
$c+na=aq+na=a(q+n)=ax$
where
$x=qn$
is an integer, so
$a | (c+na)$
.
b) Let
$c=aq$
as in a) then
$| c |= | aq |= a | q |$
and the result follows since
$| q | \ge 1$
and
$q$
is an integer. This result implies that
$c$
has only a finite number of divisors, since any divisor must be less than or equal to
$| c |$
.
c) If
$a | b, \; b | a$
then from b)
$a \le b, \; b \le a$
. The result follows.
d) If
$a | b, \; b | c$
then there are integers
$s, \; t$
such that
$b=as, \; c=bt$
. Then
$c=ast=a(st)$
so
$a | c$
.
e) If
$a | c, \; a | d$
then there are integers
$s, \; q$
such that
$c=as, \; d=aq$
. Then
$mc+nd=mas+naq=a(ms+nq)=ax$
where
$x=ms+nq$
is an integer so e) is proved.