The family tree of 12's divisors
Tonight's idea
The divisors of 12 are 1, 2, 3, 4, 6 and 12. "Divides" puts them in an order: 2 comes before 6 because 2 divides 6. But 4 and 6 cannot be compared: neither divides the other.
Draw it. Put each number higher than the numbers that divide it. Join \(a\) up to \(b\) only when \(a\) divides \(b\) and no other number in the list fits between them. So 2 joins to 4, but not to 12, because 4 is in between.
Say \(a\) is below \(b\), and \(b\) is above \(a\), if you can get from \(b\) to \(a\) going down lines only. That happens exactly when \(a\) divides \(b\). A number counts as below and above itself.
Take two divisors of a positive whole number. Of the numbers below both, one is best: all the others are below it. It is their gcd. Of the numbers above both, one is best: it is below all the others. It is their lcm. An order where every pair has both is called a lattice.
Watch one: the divisors of 12
Four layers and seven lines. Every line multiplies by one prime: by 2 going up to the left, by 3 going up to the right.
Best below 4 and 6. Below 4 are 4, 2 and 1. Below 6 are 6, 3, 2 and 1. Below both: 2 and 1. Since 1 is below 2, the best is 2. That is the greatest common divisor, \(\gcd(4, 6) = 2\).
Best above 4 and 6. Above 4 are 4 and 12. Above 6 are 6 and 12. Above both: only 12. That is the least common multiple, \(\operatorname{lcm}(4, 6) = 12\).
Careful. 3 is drawn lower than 4, but it is not below 4, because 3 does not divide 4.
Your turn
- The divisors of 30 are 1, 2, 3, 5, 6, 10, 15 and 30. (a) Draw the diagram in four layers: 1, then 2, 3, 5, then 6, 10, 15, then 30. (b) How many lines did you draw? Which solid shape does the picture look like? (c) \(12 = 2 \times 2 \times 3\) also has three prime factors. Why is its picture not this shape?
- (a) Draw the diagram for the divisors of 16. (b) Here, which is the best below and which is the best above for any two different numbers? (c) Find another number whose diagram has this shape.
- Use your diagram for 30. (a) Find the best below (gcd) and the best above (lcm) for 6 and 10, for 2 and 15, and for 3 and 6. (b) Work out \(\gcd(6, \operatorname{lcm}(10, 15))\). Then work out \(\operatorname{lcm}(\gcd(6, 10), \gcd(6, 15))\). What do you notice?
- Now keep only four numbers: 2, 3, 12 and 18, still ordered by "divides". (a) Draw the diagram, with the same rule for lines. (b) Which numbers in the list are above both 2 and 3? (c) Is one of them the best? Is this order a lattice?
Stretch: sets in disguise
Write down all eight subsets of \(\{x, y, z\}\), from the empty set \(\{\}\) up to \(\{x, y, z\}\) itself. Say one set is below another when everything in it is also in the other. Draw the diagram in layers by size. Why is it the same picture as the divisors of 30? What do gcd and lcm turn into?
Answers
- (a) See the picture. Each line multiplies by one prime. (b) 12 lines. It looks like a cube standing on one corner: 8 corners and 12 edges. (c) A cube needs 8 corners, and 12 has only 6 divisors. In 30 the three primes are different, so each one is either in a divisor or not: \(2 \times 2 \times 2 = 8\) divisors. In 12 the prime 2 is used twice, and the picture is two squares side by side.
- (a) One column: 1, 2, 4, 8, 16, with four lines. (b) Every pair can be compared, so the best below is the smaller of the two and the best above is the larger. (c) 81 works: its divisors are 1, 3, 9, 27, 81. So does any prime multiplied by itself four times, such as \(5 \times 5 \times 5 \times 5 = 625\).
- (a) For 6 and 10: gcd 2, lcm 30. For 2 and 15: gcd 1, lcm 30. For 3 and 6: gcd 3, lcm 6, because 3 is already below 6. (b) \(\operatorname{lcm}(10, 15) = 30\) and \(\gcd(6, 30) = 6\). On the other side \(\gcd(6, 10) = 2\), \(\gcd(6, 15) = 3\) and \(\operatorname{lcm}(2, 3) = 6\). Both are 6. In fact \(\gcd(a, \operatorname{lcm}(b, c)) = \operatorname{lcm}(\gcd(a, b), \gcd(a, c))\) for any three positive whole numbers, the same pattern as \(a \times (b + c) = a \times b + a \times c\). A lattice that obeys this rule is called distributive. Some lattices do not.
- (a) Four lines: 2 to 12, 2 to 18, 3 to 12 and 3 to 18. (b) 12 and 18. (c) No. The best one would have to be below the other, but 12 does not divide 18 and 18 does not divide 12. So 2 and 3 have no best one above, and this order is not a lattice. Being the smaller number does not make 12 best: "below" means "divides" here. Among all whole numbers the best above 2 and 3 is 6, but 6 is not in the list.
Stretch. The layers are \(\{\}\); then \(\{x\}, \{y\}, \{z\}\); then \(\{x, y\}, \{x, z\}, \{y, z\}\); then \(\{x, y, z\}\). Swap \(x\) for 2, \(y\) for 3 and \(z\) for 5, and multiply whatever is in the set. The empty set gives 1, and \(\{x, z\}\) gives \(2 \times 5 = 10\). Because \(30 = 2 \times 3 \times 5\) uses each prime once, every divisor comes from exactly one subset. One divisor divides another exactly when all its primes are among the other's, that is, when its set is inside the other set. So the two orders match, line for line. The gcd turns into "the things in both sets" and the lcm into "the things in either set": 6 and 10 are \(\{x, y\}\) and \(\{x, z\}\), in both is \(\{x\}\), which is 2, and in either is \(\{x, y, z\}\), which is 30. The same trick fails for 12: it has 6 divisors, and no set has exactly 6 subsets.