#math trivia for #February11:42 is the second smallest tricomposite:42 = 2*3*7; what are its eight divisors?
— Burt Kaliski Jr. (@modulomathy) February 11, 2012
Tricomposite is not in the dictionary, but its definition should be clear from context: a tricomposite number is the product of three primes. Bicomposite numbers are common in cryptography — the security of the RSA algorithm is based on the difficulty of finding the prime factors of a number that typically has two large prime factors. (“Multi-prime RSA” involves three or more prime factors, so tricomposites would appear in that version of the algorithm.)
Suppose a number n is the product of exactly three distinct primes, p, q, and r:
n = pqr .
Then n is also divisible by the product of any subset of the primes. In addition to p, q, and r, it’s also divisible by these numbers:
pq
pr
qr
pqr
Finally, n is also divisible by 1. All together, this makes eight divisors. (As is standard, negative numbers are not counted, and only integers are considered in these types of problems.)
Another way of counting the eight divisors is to consider that each of the primes can either be included or not included in the divisor, so there are 2*2*2 = 8 ways to construct a divisor. A bicomposite, by similar reasoning, has four divisors.
Are all eight divisors distinct? Yes. Consider two divisors paqbrc and pdqerf with a different arrangement of exponents (each exponent is 0 or 1), and suppose the divisors were not distinct, i.e.:
paqbrc = pdqerf .
Let’s simplify the equation. If a prime factor isn’t included in a divisor (i.e., the exponent is 0), drop it from the formula. If it’s included on both sides (i.e., the corresponding exponents are 1), drop both occurrences. After the simplification, each prime will therefore appear on at most one side of the equation. But if a prime appears on one side, this means that the other side must be divisible by that prime as well — which can’t happen because a prime is by definition divisible by only 1 and itself. So, after the simplication, no primes can remain, which means that a = d, b = e, and c = f: the two arrangements of exponents are not different, a contradiction. Each of the eight divisors therefore is distinct from the other seven.
Could there be another divisor involving a fourth prime? No, because the fourth prime would have to divide p, q, or r.
Now back to the problem: 42 is the product of three distinct prime factors, 2, 3 and 7, so we have p = 2, q = 3, and r = 7. The eight divisors of 42 are therefore
1
2
3
2*3 = 6
7
2*7 = 14
3*7 = 21
42 .
modulomathy.com 