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<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:


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?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.