## Confounding Factors

My colleague Julia is preparing a talk about factoring for an elementary audience, and she created the following problem to use as a warm-up:

Take a two‑digit number ab, and find the least common multiple of a, b, and ab. For example, if you take the number 35, then LCM(3, 5, 35) = 105. For which two‑digit number ab is LCM(abab) the greatest? (The notation ab is used to indicate the two‑digit number with tens digit a and units digit b, which is equal to 10a + b. This notation is used to distinguish the two‑digit number ab from the product ab.)

Here are some math jokes about factors:

What do you call an amount that exactly divides a recipe for a sweet confection?
A fudge factor.

What do algebra equations and British television have in common?
An X Factor.

Sadly, both of those are my original jokes. Sorry. To cleanse your palate, check out one of Randall Munroe’s original jokes about factoring:

Entry filed under: Uncategorized. Tags: , , , , .

• 1. xander  |  September 25, 2010 at 12:29 am

The answer to the warm up is 89.

For simplicity, let c = MAX(10a+b,10b+a).

In general, LCM(a,b,c) = a*b*c/GCD(a,b,c). Intuitively, we want to maximize the numerator while minimizing the denominator.

The smallest possible denominator occurs when a, b, and c are relatively prime, so it would be great to find three numbers that are relatively prime.

To maximize the numerator, we can start by examining the maximum possible values for a and b. So take a=9 and b=8. 9 and 8 are relatively prime, so we are in business thus far. 98 and 8 share common factor (i.e. 2), but 89 is relatively prime to both 9 and 8, so 89 is a good candidate. LCM(9,8,89) = 8*9*89 = 6408.

a=9 and b=7 is another possible candidate. 97 is relatively prime to 9 and 7, thus LCM(9,7,97) = 9*7*97 = 6111. As 6111<6408, we can dismiss 97 as a candidate number.

All other candidates are inferior to those listed above. At best, we would have LCM(a,b,c) = a*b*c, where a ≤9, b<7 and c<97. Hence a*b*c<6111<6408.

Therefore 89 is the two digit number which maximizes LCM(a,b,c).

I don’t find this solution to be entirely satisfactory, as it ultimately relies upon some brute forcing or guess-and-checking (i.e. several candidate numbers need to be selected and tested), but I can’t come up with anything better/more generalizable.

As an added note, brute forcing in C gave the same result.

xander

• 2. sfgss  |  November 20, 2017 at 2:47 pm

pooey

• 3. venneblock  |  November 20, 2017 at 3:00 pm

To which part?