Divisibility and Greatest Common Divisors
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).
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".
Before getting started, we shall review divisibility among integers mostly to set some notations and to indicate its properties
Definition 2.1. When and are integers, we say divides if for some . We then write (read as " divides ").
The set of integers is denoted , from the German word Zahl = number.
Example 2.2. We can have (because ), , and . We also have for every . However, does not divides and 0 certainly does not divides .
Divisibility is a relation, much like inequalities, instead of an operator. In particular, the relation does not spill out the number ; equivalently, should not be confused with .
Also note that divisibility is not symmetric: if , it is usually not true that , so you should never confuse the roles of and in the relation: but .
Remark 2.3. One should strictly follow the definition in Definition 2.1, rather than following the intuition " is an integer". Although they essentially mount the same (exception: but 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 with , then for any .
Proof. By definition, we have for some . Thus and , which gives the claim.
Theorem 2.5. If and then .
Proof. Now we have and for some . Then and , so .
Theorem 2.6. If and then for every .
Proof. We have and for some . Then
and , so .
In the language of linear algera, Theorem 2.6 says any factor of two integers is also a factor of any -linear combination of two integers. To avoid silly errors, keep in mind the following false implications: generally
(for instance but 6 divides neither 4 or 9) and
(for instance but does not divide ).
Greatest Common Divisors
For two nonzero integers and , their greatest common divisor is the largest integer which is a factor of both of them. It is denoted . For instance, and . Do not confuse our usage of parentheses in with the notation for open intervals in calculus. The number is always a common divisor, and it is the greatest common divisor exactly when and 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 and . Since
we have .