Muhammad's least list

First we will try to factorize out - $10004000600040001$ and if we are able to successfully factorize it out then almost $80$ % of our work is done.

Indeed $10004000600040001$ factorizes as $73^4 \times 137^4$

Now, we have $lcm(x,y) = 73^4 \times 137^4$

We know that the lcm of two numbers contains the highest power of prime factors of the two numbers. Therefore, $x$ and $y$ can only have maximum value of $73^4 \times 137^4$ . And if any of two numbers is less than this, then the other number must have the highest value of that prime factor. That means, one or the other number must contain $73^4$ and $137^4$

Now let us see the different possibilities of $(x,y)$

$\begin{array}{|c|c|} \hline \mathbf{x} & \mathbf{y} \\ \hline 73^0 & 73^4 \\ 73^1 & 73^4 \\ 73^2 & 73^4 \\ 73^3 & 73^4 \\ 73^4 & 73^4 \\ 73^4 & 73^3 \\ 73^4 & 73^2 \\ 73^4 & 73^1 \\ 73^4 & 73^0 \\ \hline \end{array}$

Thus, total of $9$ possibilities for $73^x$ . Similarly, we also get $9$ possibilities for $137^x$ $x \epsilon$ { $0,1,2,3,4$ }

Hence total of $9 \times 9 = \boxed{81}$ ordered pairs for $(x,y)$

The first step is determining that

$10004000600040001=(10^4+1)^4=10001^4=73^4137^4.$

Since 73 and 137 are both prime, in order to have lcm $(x,y)=73^4137^4$ , all of our ordered pairs must be of the form $(73^a 137^b,73^c 137^d)$ , where a , b , c , and d are all integers from 0 to 4 (inclusive), and $\max(a,c)=\max(b,d)=4$ .

There are 9 distinct ordered pairs of integers $(a,c)$ for which $0\leq a,c \leq 4$ and $max(a,c)=4$ , and likewise 9 distinct ordered pairs of integers $(b,d)$ for which the same is true. This makes for $9 \times 9 = 81$ distinct ordered pairs $(73^a 137^b,73^c 137^d)$ whose lcm is 10004000600040001.

Note:

• $10004000600040001 = 73^4 \times 137^4$
• So it has $(4+1) \times (4+1) = 25$ divisors. (Briefly, each divisor is of the form $73^i \times 137^j$ where $i=0..4$ and $j=0..4$ . For a more detailed explanation see http://mathschallenge.net/library/number/number of divisors )
• At least one of $x$ and $y$ has to divide $73^4$ and at least one of $x$ and $y$ has to divide $137^4$ . Otherwise $73^4 \times 137^4$ wouldn't be their LCM.

4 cases:

1. If $x = 73^4 \times 137^4 \Rightarrow y$ can be any factor $\Rightarrow 25$ options.
2. If $y = 73^4 \times 137^4 \Rightarrow x$ can be any factor $\Rightarrow 24$ options as we've already counted the one where both $x$ and $y$ are $73^4 \times 137^4$ in case 1.
3. If $73^4$ divides $x$ and we're not in case 1, then $137^4$ has to divide $y \Rightarrow 4$ options for $x$ and $4$ options for $y \Rightarrow 16$ options.
4. Opposite of case 3 $\Rightarrow 16$ options.

Total $25+24+16+16=\boxed{81}$ options.

Notice that in the number $\textbf{1}000\textbf{4}000\textbf{6}000\textbf{4}000\textbf{1}$ there are the binomial coefficients $[1, 4, 6, 4, 1]$ , at the 5th row of Pascal's Triangle. We can use powers of 10 to construct this number as such:

$\,\,\,\,(10^n + 1)^4 = (1)10^{4n} + (4)10^{3n} + (6)10^{2n} + (4)10^{n} + (1)$

So by speculation, $10004000600040001 = (10^4 + 1)^4 = 10001^4$ .

The prime factorization of 10001 is $73\cdot137$ . We now must solve,

$\,\,\,\,lcm(x, y) = 73^4\cdot137^4$

So both $x$ and $y$ must be of the form $73^a\cdot137^b$ , with $a, b \in \left\{ {0, 1, 2, 3, 4} \right\}$ . We can also deduce that at least one of $x$ and $y$ must have $a$ or $b = 4$ , so that the LCM will be exactly $73^4\cdot137^4$ .

Now to count the possibilities. We will look at each prime separately. For $73$ , one of $x$ and $y$ must have an exponent of $4$ , so we will assume that this is $x$ , and later multiply by 2. Now, $y$ can be any value from 0 to 3, giving it 4 possible values. So we have, for the prime factor 73, $2\cdot4 = 8$ possibilities, plus the possibility that both $x$ and $y$ will have an exponent of $4$ , so that gives $9$ .

Clearly for the prime $137$ the same is true, so the total amount of ordered pairs of $(x, y)$ is,

$\,\,\,\,9\cdot9 = \boxed{81}$

Note that $10004000600040001 = 10001^4 = 73^4 \cdot 137^4$ . (Motivation, the number looks like $14641 = 11^4$ .

Let $x = 73^a \cdot 137^c, y = 73^b \cdot 137^d$ . Then, $max(a, b) = max(c, d) = 4$ . We consider four cases :

a) $a = b, c = d$ , there is only $1$ solution in this case, that is $a = b = c = d = 4$ .

b) $a = b, c \neq d$ , there are $8$ solutions, because $a = b = 4$ , we just have to choose $c$ and $d$ . If $c > d$ , then there are $4$ choices for $d$ and only $1$ for $c$ , similarly, if $d > c$ , there are only $4$ choices.

c) $a \neq b, c = d$ , this case is analogous to b), there is also $8$ cases.

d) $a \neq b, c \neq d$ . Suppose, $a > b, c > d$ , then there are $4 \cdot 4 = 16$ solutions. ( $4$ choices for $b$ and $4$ choices for $c$ .) There are $3$ more similar cases, namely when $a > b, c < d$ , $a < b, c > d$ and $a < b, c < d$ . This gives a total of $64$ solutions.

Thus, there are a total of $1 + 8 + 8 + 64 = \boxed{81}$ solutions.

see that 10004000600040001 = (73^4 ) (137^4) The least common multiple to two numbers is [p_{1}^{max(r_{1a}, r_{1b} } ] [ p {2}^max{r {2a},r_{2b}}] where the prime factorization for x = (p1)^n* (p2^m), and y =( p1^k)*( p2^j) here max(n,k)=4 and max(m,j)=4 we have ordered pairs (n,k) as follows let k = 4, then n can be 0,1,2,3,4, next let n = 4 then k can be 0,1,2,3,4 So total number of distinct ways to have 4 = max(n,m) = 5 + 5 - 1 = 9 where we have subtracted the case (4,4) because it is counted twice. Same goes for 4 = max(m,k), there are 9 different ways to construct p2^m , p2^j such that the maximum is p2^4 Hence total no. of ordered pairs is 9 x 9 = 81 pairs

10004000600040001=10^16 + 4 10^12 + 6 10^8+ 4 10^4 +1=(10^4 +1)^4=73^4 137^4 Lcm contains the highest index power among the prime factorisation two numbers of each prime.

so atleast one of the numbers contain 73^4 and the other can have 73^0 or 73^1, or 73^2 or 73^3 giving a total of 4 cases. but considering the that (x,y) is ordered pair we get 4 more cases (reverse of above) and also the case where both contain 73^4. so gives a total of 9 cases. similarly for 137^4 we get 9 cases. total number of ordered pairs = 9*9=81