Divisibility and Greatest Common Divisors DRAFT


Yesterday morning, our AP CSA teacher, the good old Bharati, assigned us an College Board's official free response question. When we were asked to recursively find the greatest common divisor of two integers, I was sated, in that in such a class for dummies students finally have chance to learn about one of the few classic and ingenious algorithms that evolved before the Common Era (AD).

College Board's FRQ Progress Check 10
College Board's FRQ Progress Check 10

This excitement, however, was washed away this morning when we received the grading guideline. In it, College Board did not provide a proof of correctness of its solution that uses Euclidean algorithm, but merely threw readers a block of code, as if saying, "Here you go, problem solved".

Divisibility Relation

Before getting started, we shall review divisibility among integers mostly to set some notations and to indicate its properties

Definition 2.1. When aa and bb are integers, we say aa divides bb if b=akb=ak for some kZk \in \Z. We then write aba \mid b (read as "aa divides bb").

The set of integers is denoted Z\Z, from the German word Zahl = number.

Example 2.2. We can have 262 \mid 6 (because 6=236 = 2 \cdot 3), 4(12)4 \mid (-12), and 505\mid 0. We also have ±1a\pm 1 \mid a for every aZa \in \Z. However, 66 does not divides 33 and 0 certainly does not divides 55.

Divisibility is a relation, much like inequalities, instead of an operator. In particular, the relation 262 \mid 6 does not spill out the number 33; equivalently, 2<62 < 6 should not be confused with 626-2.

Also note that divisibility is not symmetric: if aba\mid b, it is usually not true that bab \mid a, so you should never confuse the roles of aa and bb in the relation: 262 \mid 6 but 626 \nmid 2.

Remark 2.3. One should strictly follow the definition in Definition 2.1, rather than following the intuition "ab\frac a b is an integer". Although they essentially mount the same (exception: 000 \mid 0 but 00\frac 0 0 is undefined), thinking about divisibility in terms of ratios can easily screw up your understanding of divisibility of in other scenarios in algebra. Nonetheless, it is best to regard Definition 2.1.

Next I shall throw a couple of theorems about divisibility that are no more than simple applications of the difinition. They all make intuitive sense.

Theorem 2.4. Let a,bZa,b \in \Z with aba \mid b, then abca\mid bc for any cZc \in \Z.

Proof. By definition, we have b=akb = ak for some kZk \in \Z. Thus bc=(ak)c=a(kc)bc = (ak)c = a(kc) and kcZkc \in \Z, which gives the claim. \square

Theorem 2.5. If aba \mid b and bcb \mid c then aca \mid c.

Proof. Now we have b=akb=ak and c=blc=bl for some k,lZk,l \in \Z. Then c=bl=(ak)l=a(kl)c = bl = (ak)l =a(kl) and klZkl \in \Z, so aca\mid c. \square

Theorem 2.6. If aba\mid b and aca\mid c then a(br+cs)a\mid (br+cs) for every r,sZr,s \in \Z.

Proof. We have b=akb = ak and c=alc = al for some k,lZk,l \in \Z. Then

br+cs=(ak)r+(al)s=a(kr+ls)br + cs = (ak)r + (al)s = a(kr+ls)

and kr+lsZkr + ls \in \Z, so a(br+cs)a\mid (br+cs). \square

In the language of linear algera, Theorem 2.6 says any factor of two integers is also a factor of any Z\Z-linear combination of two integers. To avoid silly errors, keep in mind the following false implications: generally

abc⇏ab or aca \mid bc \not\Rightarrow a \mid b\ \textrm{or}\ a\mid c

(for instance 6(49)6 | (4 \cdot 9) but 6 divides neither 4 or 9) and

abn⇏aba \mid b^n \not\Rightarrow a \mid b

(for instance 126612 \mid 6^6 but 1212 does not divide 66).

Greatest Common Divisors

For two nonzero integers aa and bb, their greatest common divisor is the largest integer which is a factor of both of them. It is denoted (a,b)(a,b). For instance, (12,18)=6(12, 18) = 6 and (9,15)=3(-9,15)=3. Do not confuse our usage of parentheses in (a,b)(a,b) with the notation for open intervals in calculus. The number 11 is always a common divisor, and it is the greatest common divisor exactly when aa and bb are relatively prime.

The naive approach of finding the greatest common divisor of two integers in to factor each into primes and extract the greatest common divisor from the prime power factors that appear.

Example 3.1. Consider a=19088597a = 19088597 and b=39083b = 39083. Since

19088597=11219323, 39083=1121719,19088597 = 11^2 \cdot 19^3 \cdot 23,\ 39083 = 11^2 \cdot 17 \cdot 19,

we have (19088597,39083)=11219=2299(19088597, 39083) = 11^2 \cdot 19 = 2299.

Gaussian Integral ▶