Maths Olympiad Prep

Library / /193 of 348

Number theory Difficulty 4.9 AIME Find the answer

For positive integers nn, let L(n)L(n) be the largest factor of nn other than nn itself. Determine the number of ordered pairs of composite positive integers (m,n)(m, n) for which L(m)L(n)=80L(m) L(n)=80.

A number or a short expression. Spacing and $ signs are ignored.

Solution

Let xx be an integer, and let pxp_{x} be the smallest prime factor of xx. Then, if L(a)=xL(a)=x, we note that we must have a=pxa=p x for some prime ppxp \leq p_{x}. (Otherwise, if p>pxp>p_{x}, then pxpx>x\frac{p x}{p_{x}}>x. If pp is composite, then kx>xk x>x for some factor kk of xx.)

So we have:
- L(a)=2,4,8,10,16,20,401L(a)=2,4,8,10,16,20,40 \Rightarrow 1 value for aa
- L(a)=53L(a)=5 \Rightarrow 3 values for aa

Hence, we note that, since mm and nn are composite, we cannot have L(m)=1L(m)=1 or L(n)=1L(n)=1, so the possible pairs (L(m),L(n))(L(m), L(n)) are (2,40),(4,20),(5,16),(8,10)(2,40),(4,20),(5,16),(8,10) and vice-versa.

We add the number of choices for each pair, and double since mm and nn are interchangeable, to get 2(1×1+1×1+3×1+1×1)=122(1 \times 1+1 \times 1+3 \times 1+1 \times 1)=12 possible ordered pairs (m,n)(m, n).

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.