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

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?

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$$.

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 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}.$$

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?