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?
 A: 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}.$$
A: 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$.
A: 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?
