Mathematics for Computer Science

Chapter 8 Number Theory186

1. Ifajbandbjc, thenajc.


2. Ifajbandajc, thenajsbCtcfor allsandt.


3. For allc¤ 0 ,ajbif and only ifcajcb.

Proof. These facts all follow directly from Definition 8.1.1, and we’ll just prove
part 2. for practice:
Given thatajb, there is somek 12 Zsuch thatak 1 Db. Likewise,ak 2 Dc,
so
sbCtcDs.k 1 a/Ct.k 2 a/D.sk 1 Ctk 2 /a:

ThereforesbCtcDk 3 awherek 3 WWD.sk 1 Ctk 2 /, which means that

ajsbCtc:



A number of the formsbCtcis called aninteger linear combinationofbandc,
or a plainlinear combination, since in this chapter we’re only talking integers. So
Lemma 8.1.3.2 can be rephrased as

Ifadividesbandc, thenadivides every linear combination ofbandc.

We’ll be making good use of linear combinations, so let’s get the general definition
on record:

Definition 8.1.4.An integernis alinear combinationof numbersb 0 ;:::;bniff

nDs 0 b 0 Cs 1 b 1 C


Csnbn

for some integerss 0 ;:::;sn.

8.1.2 When Divisibility Goes Bad

As you learned in elementary school, if one number doesnotevenly divide another,
you get a “quotient” and a “remainder” left over. More precisely:

Theorem 8.1.5. [Division Theorem]^2 Letnanddbe integers such thatd > 0.
Then there exists a unique pair of integersqandr, such that

nDq
dCrAND 0 r < d: (8.1)

(^2) This theorem is often called the “Division Algorithm,” even though it is not what we would call
an algorithm. We will take this familiar result for granted without proof.