1.1   Divisors and GCDs

In the Prelab section of this chapter, you had the opportunity to compute the divisors of some integers by hand. The applet below will automatically compute all of the positive divisors for a given integer. Give it a try:

Your browser does not support java.

The output is the set of all the positive divisors of 12345. We only list the positive divisors because it is easy to compute all of the divisors from these. We would just have to take these numbers and their negations to get all of the divisors of 12345.

In the Prelab section, an illustration was given that showed how to compute gcd(45, 60). The first step is to compute the positive divisors of both 45 and 60. Here are the divisors of 45:

Your browser does not support java.

And here are the divisors of 60:

Your browser does not support java.

The last step is to pick out the largest number that occurs in both lists. A handy way to do this in one shot is to use the applet below. This applet takes two integers as input, and produces the set of positive divisors shared by both input values.

Your browser does not support java.

With no work at all it is clear that gcd(45, 60) = 15. The above example is cool, but after all, you could do that one by hand. Let's try some larger choices:

Your browser does not support java.

Imagine trying to do this one by hand! By the way, what is gcd(a, b)? Once you figure it out, use the applet below to compute the positive divisors of gcd(a, b). (Replace ??? with the value of gcd(a, b).)

Your browser does not support java.

Research Question 1

In the preceding computations, we have found the set of common positive divisors of a = 223092870 and b = 6227020800, and have found the set of positive divisors of gcd(a, b). Compare these two sets. Change the values of a and b, and repeat the experiment: compute the set of common positive divisors of a and b, compute the set of positive divisors of gcd(a, b), and compare the two sets. Once you think you see a pattern, state a conjecture and try to prove it!

Hints: Since your conjecture will involve sets, when working on the proof you should keep in mind the suggestions concerning proofs involving sets in the "Tips for Writing Proofs" section of the Course Guide. Also, you may find it helpful to use the results in the "GCDs and Factorization" section below when working on your proof.

Section 1.1 | Section 1.2 | Section 1.3 | Section 1.4 | Section 1.5