1.3: Elementary Divisibility Properties

Definition \(\PageIndex{1}\)

\(d\mid n\) means there is an integer \(k\) such that \(n=dk\). \(d\nmid n\) means that \(d\mid n\) is false.

Note that \(a\mid b\neq a/b\). Recall that \(a/b\) represents the fraction \(\frac ab\).

The expression \(d\mid n\) may be read in any of the following ways:

1. \(d\) divides \(n\).
2. \(d\) is a divisor of \(n\).
3. \(d\) is a factor of \(n\).
4. \(n\) is a multiple of \(d\).

Thus, the following five statements are equivalent, that is, they are all different ways of saying the same thing.

1. \(2 \mid 6\).
2. 2 divides 6.
3. 2 is a divisor of 6.
4. 2 is a factor of 6.
5. 6 is a multiple of 2.

Definitions will play an important role in this course. Students should learn all definitions and be able to state them precisely. An alternative way to state the definition of \(d\mid n\) is as follows.

Definition \(\PageIndex{2}\)

\(d\mid n\iff n=dk \text{ for some }k\).

or maybe

Definition \(\PageIndex{3}\)

\(d\mid n\) iff \(n=dk\) for some \(k\).

Keep in mind that we are assuming that all letters \(a,b,\dotsc,z\) represent integers. Otherwise we would have to add this fact to our definitions. One might also see the following definition sometimes.

Definition \(\PageIndex{4}\)

\(d\mid n\) if \(n=dk\) for some \(k\).

Note that \(\iff\), iff, and if and only if, all mean the same thing. In definitions such as Definition \(\PageIndex{4}\) if is interpreted to mean if and only if. It should be emphasized that all the above definitions are acceptable. Take your pick. But be careful about making up your own definitions.

Theorem \(\PageIndex{1}\): Divisibility Properties

If \(n\), \(m\), and \(d\) are integers then the following statements hold:

1. \(n\mid n\) (everything divides itself)
2. \(d\mid n\) and \(n\mid m\ \Longrightarrow d\mid m\) (transitivity)
3. \(d\mid n\) and \(d\mid m\ \Longrightarrow d\mid an+bm\) for all \(a\) and \(b\) (linearity property)
4. \(d\mid n\Longrightarrow ad\mid an\) (multiplication property)
5. \({ad}\mid{an}\) and \(a\ne 0\) \(\Longrightarrow\) \(d\mid n\) (cancellation property)
6. \(1\mid n\) (one divides everything)
7. \(n\mid 1\Longrightarrow n=\pm 1\) (\(1\) and \(-1\) are the only divisors of \(1\).)
8. \(d\mid 0\) (everything divides zero)
9. \(0\mid n\Longrightarrow n=0\) (zero divides only zero)
10. If \(d\) and \(n\) are positive and \(d\mid n\) then \(d\le n\) (comparison property)

Exercise \(\PageIndex{1}\)

Prove each of the properties \(1\) through \(10\) in Theorem \(\PageIndex{1}\).

Definition \(\PageIndex{5}\): Linear Combination

If \(c=as+bt\) for some integers \(s\) and \(t\) we say that \(c\) is a linear combination of \(a\) and \(b\).

Thus, statement 3 in Theorem \(\PageIndex{1}\) says that if \(d\) divides \(a\) and \(b\), then \(d\) divides all linear combinations of \(a\) and \(b\). In particular, \(d\) divides \(a+b\) and \(a-b\). This will turn out to be a useful fact.

Exercise \(\PageIndex{2}\)

Prove that if \(d \mid a\) and \(d \mid b\) then \(d\mid a-b\).

Exercise \(\PageIndex{3}\)

Prove that if \(a \in \mathbb{Z}\) then the only positive divisor of both \(a\) and \(a+1\) is \(1\).