What are the number of ordered pairs $(x,y)$ where both $x$ and $y$ divide $20^{19}$, however $xy$ doesn't?

Question

What are the number of ordered pairs $(x,y)$ where both $x$ and $y$ divide $20^{19}$, however $xy$ doesn't?

I started by taking the prime factorization of $20^{19}$ to get : $2^{38}5^{19}$.

I then noticed, that the only way for $xy$ to not divide this number was if the powers of $x$ and $y$ add to greater than $38$ or $19$. For example, if $x=2^{38}$ and $y = 2^{2}$, then $xy$ would be $2^{40}$ which would not divide $2^{38}5^{19}$ evenly.

My question is, what would be the total number of ordered pairs?

Answer 1

Well, If $x = 2^a5^c$ and $y = 2^b5^d$

thenn we have $a+b > 38$ or $c+d > 19$.

To have $a+b > 38$ while $a \le 38$ and $b \le 38$ if we have $a = k$ then $b$ can be as small as $39-k$ and can be as large as $38$. Those are $k$ options. $(38+1) - (39-k) = k$. So there are $\sum_{k=1}^{38}k = \frac {38*39}2 = 741$ such pairs.

And likes there are $\sum_{k=1}^{19} k = 190$ such possible pairs.

If $(a,b)$ is such a pairc $c,d$ can be anything from $0$ to $19$. Thatn is $20^2 = 400$ options.

So there are $741*400$ pairs where $a+b > 38$.

Like wise there are $190*39^2$ pairs were $c + d > 19$.

But we counted all the pairs where $a+b > 38$ and $c+d >19$ twice! So we must subtract that number of pairs. There are $190*741$ so pairs.

So the total number of pairs where $a+b>38$ or $c+d > 19$ or both is

$741*400+190*39^2 - 190*741$.

Answer 2

You have made good progress. Now let $x=2^a5^b, y=2^cy^d$. This lets you work with the exponents. Your observations can be expressed as you need $a,b \le 38, c,d \le 19$ and either $a+b \gt 38$ or $c+d \gt 19$ (or both). Can you count the possibilities from that?

Answer 3

There are $39^220^2$ pairs of divisors, with no restrictions.

There are $\binom{40}{2}\binom{21}{2}$ pairs of divisors such that the product is also a divisor.

This is because if $0\leq a_1< a_2\leq 39$ and $0\leq b_1<b_2\leq 20$ you get a pair of divisors $$d_1=2^{a_1}5^{b_1}, d_2=2^{a_2-a_1-1}5^{b_2-b_1-1},$$ and these are all such pairs.

So the pairs of divisors with the product not a divisor is the difference:

$$39^220^2-\binom{40}2\binom{21}{2}$$

---

More generally, let $\rho_k(n)$ be the number of $k$-tuples of natural numbers such $(d_1,\dots,d_k)$ such that $d_1d_2\cdots d_k\mid n.$

Then we see that $\rho_k$ is multiplicative - $\rho_k(mn)=\rho_k(m)\rho_k(n)$ if $\gcd(m,n)=1.$

Also, $\rho_k(p^a)=\binom{a+k}{k}.$

So if $n=p_1^{a_1}\cdots p_m^{a_m}$ then the number of $k$-tuples $(d_1,\dots,d_k)$ of divisors or $n$ whose product is not a divisor of $n$ is:

$$\tau(n)^k - \rho_k(n)=\prod_{i=1}^{m}(a_i+1)^k - \prod_{i=1}^{m}\binom{a_i+k}{k}.$$