1.4: Elementary Divisibility Properties

Definition \(\PageIndex{1}\)

We write \(d\mid n\) if there is an integer \(k\) such that \(n=dk\). The notation \(d\nmid n\) means that \(d\mid n\) is false.

Note that \(a\mid b\) does not mean the same thing as \(a/b\). Recall that \(a/b\) represents the fraction \(\frac ab\), a mathematical “noun.” The notation \(a\mid b\) represents a complete mathematical statement or sentence.

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\) if and only if \(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\) and if and only if 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)

We end this chapter with one more definition, that will be important in the chapters that follow.

Definition \(\PageIndex{5}\)

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, so we emphasize it in the exercises.

Exercises

Exercise \(\PageIndex{1}\)

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

Exercise \(\PageIndex{2}\)

Prove that if \(b \neq 0\) then \(b\mid a\) if and only if \(a/b\in\mathbb{Z}\).

(As said earlier, one difficulty some students have with the “divides” notation is confusing its vertical bar with a fraction bar—the two bars are not the same. One (namely, \(\mid\) ) represents a relationship; the other (namely, \(/\) or – ) represents a binary operation. In your answer, pay particular care that you are using the correct bar in each place.)

Exercise \(\PageIndex{3}\)

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

Exercise \(\PageIndex{4}\)

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

Exercise \(\PageIndex{5}\)

Prove that \(x+y\) is divisor of \(x^n+y^n\) for all odd positive integers \(n\).

(Hint: it might be helpful to consider the result proved in Exercise 1.3.12; you may use it here, if desired, without supplying the proof.)

Exercise \(\PageIndex{6}\)

1. Use induction to prove that \((6n+1)^2-1\) is divisible by 4 for every integer \(n \geq 0\).
2. Prove the same statement from part (a) without using induction by expanding \((6n+1)^2-1\).

Exercise \(\PageIndex{7}\)

1. Prove by induction, not relying on any of the exercises from the previous chapter, that \(7^n-1\) is divisible by 6 for every positive integer \(n\).
2. Now substitute one or more values for \(n\) in an exercise from the previous chapter to find a simpler proof of the statement in part (a). (Something to think about: how does your proof in part (a) compare to the proof in the exercise you used from the previous chapter?)