The d(ij) identity: why coprime pairs biject to divisors
Let $d(u)$ denote the number of positive divisors of $u$. The following identity is a staple of number-theoretic manipulations (and competitive programming):
$$ \sum_{i=1}^{n}\sum_{j=1}^{m} d(ij) \;=\; \sum_{i=1}^{n}\sum_{j=1}^{m}\sum_{x\mid i}\sum_{y\mid j}[\gcd(x,y)=1]. $$The claim is that for any fixed positive integers $i,j$:
$$ d(ij)=\sum_{x\mid i}\sum_{y\mid j}[\gcd(x,y)=1], $$i.e. the number of divisors of $ij$ equals the number of ordered pairs $(x,y)$ with $x\mid i$, $y\mid j$, and $\gcd(x,y)=1$.
The proof reduces to prime powers and then constructs a bijection. Both steps are short, but the bijection hides a subtlety that tripped me up several times before it clicked.
Reducing to prime powers
Since both sides are multiplicative in $(i,j)$ (as functions of $ij$), it suffices to verify the identity when $i=p^a$ and $j=p^b$ for a single prime $p$.
Left side. $d(p^{a+b})=a+b+1$.
Right side. We need $x\mid p^a$, $y\mid p^b$, and $\gcd(x,y)=1$. Write $x=p^\alpha$, $y=p^\beta$ with $0\le\alpha\le a$, $0\le\beta\le b$. The coprimality constraint $\gcd(p^\alpha,p^\beta)=1$ forces $\min(\alpha,\beta)=0$: at least one of $\alpha,\beta$ must be zero.
Counting:
- $\beta=0$: $\alpha$ ranges over $0,1,\dots,a$ — that is $a+1$ pairs.
- $\alpha=0,\;\beta\ge 1$: $\beta$ ranges over $1,2,\dots,b$ — that is $b$ pairs.
Total $=(a+1)+b=a+b+1$. Done.
The multiplicativity argument then gives the identity for all $i,j$.
The bijection hiding behind the count
The counting argument above is clean but slightly unsatisfying: it proves two quantities are equal without showing which divisor of $ij$ each coprime pair $(x,y)$ corresponds to.
There is in fact a concrete bijection, and spelling it out resolved every confusion I had.
Encoding: divisor $\to$ coprime pair
Fix a prime $p$ with $v_p(i)=a$ and $v_p(j)=b$. Every divisor $D$ of $ij$ satisfies $0\le v_p(D)\le a+b$. Set $k=v_p(D)$ and define the $p$-component of the pair $(x,y)$ by:
- If $k\le a$: set $(v_p(x),\;v_p(y))=(k,\;0)$.
- If $k > a$: set $(v_p(x),\;v_p(y))=(0,\;k-a)$.
Do this independently for every prime $p$ dividing $ij$. The resulting $(x,y)$ satisfies:
- $x\mid i$, because $v_p(x)\le a$ for every $p$.
- $y\mid j$, because when $k>a$ we have $v_p(y)=k-a\le b$, and when $k\le a$ we have $v_p(y)=0\le b$.
- $\gcd(x,y)=1$, because for every prime $p$, at least one of $v_p(x),v_p(y)$ is zero.
Decoding: coprime pair $\to$ divisor
Given a valid $(x,y)$ with $x\mid i$, $y\mid j$, $\gcd(x,y)=1$, recover $D$ by:
- If $v_p(y)=0$: set $v_p(D)=v_p(x)$.
- If $v_p(x)=0$ and $v_p(y)\ge 1$: set $v_p(D)=a+v_p(y)$.
Since $\gcd(x,y)=1$, every prime falls into exactly one of these two cases. And since $v_p(x)\le a$ in the first case, we get $v_p(D)\le a$; in the second, $v_p(D)=a+v_p(y)\ge a+1$. So the two cases produce disjoint ranges of $k$, and every $k\in\{0,\dots,a+b\}$ is hit exactly once.
That is the bijection.
The confusions I had to work through
Confusion 1: “Isn’t this just counting LCMs? Won’t $(x,y)$ and $(y,x)$ double-count?”
My first instinct was that the right side counts ordered pairs whose LCM equals some divisor of $ij$, so swapping $x$ and $y$ would count the same divisor twice.
This is wrong because $x$ and $y$ live in different pools: $x$ must divide $i$ and $y$ must divide $j$. Even when $i=j$, the pair $(x,y)=(p,1)$ and the pair $(x,y)=(1,p)$ are both legitimate, and they correspond to different divisors of $ij$ under the bijection above.
The encoding makes this concrete. Suppose $i=j=p^2$ (so $a=b=2$).
| $k = v_p(D)$ | Divisor $D$ | Encoded pair $(v_p(x), v_p(y))$ |
|---|---|---|
| 0 | $1$ | $(0,0)$ |
| 1 | $p$ | $(1,0)$ |
| 2 | $p^2$ | $(2,0)$ |
| 3 | $p^3$ | $(0,1)$ |
| 4 | $p^4$ | $(0,2)$ |
The pair $(p,1)$ encodes $D=p$, while $(1,p)$ encodes $D=p^3$. No double-counting.
Confusion 2: “$D$ is not the product $x \cdot y$”
A natural but incorrect assumption is that the bijection sends $(x,y)$ to $D=xy$. It doesn’t.
In the table above, the pair $(1,p)$ corresponds to $D=p^3$, not $D=1\cdot p=p$.
The encoding is not a multiplicative map. Instead, it is a piecewise-linear map on exponent vectors: for each prime, the exponent of $D$ is either $v_p(x)$ or $a+v_p(y)$, depending on which side is nonzero.
The key insight is that $a$ (the exponent of $p$ in $i$) acts as an offset. When the encoding assigns a power to $y$, it means “$i$’s capacity for $p$ is full; the remaining $v_p(y)$ units of $p$ sit on top of $a$.”
Confusion 3: “When $a = b$, how do $(a,0)$ and $(0,a)$ encode different divisors?”
This was the sharpest version of my double-counting worry. With $a=b$, both $(v_p(x),v_p(y))=(a,0)$ and $(0,a)$ involve the same number $a$, so they “look the same.”
But the encoding maps them to different exponents of $D$:
- $(a,0)$: $k=a$, so $D$ contains $p^a$.
- $(0,a)$: $k=a+a=2a$, so $D$ contains $p^{2a}$.
The asymmetry comes entirely from the offset rule: powers assigned to $y$ sit above $a$, not at the bottom.
Confusion 4: “When $b < a$, what covers the small divisors?”
Suppose $a=3$, $b=1$, so $ij=p^4$.
| $k$ | $D$ | Pair $(v_p(x), v_p(y))$ | Rule |
|---|---|---|---|
| 0 | $1$ | $(0,0)$ | $k\le a$ |
| 1 | $p$ | $(1,0)$ | $k\le a$ |
| 2 | $p^2$ | $(2,0)$ | $k\le a$ |
| 3 | $p^3$ | $(3,0)$ | $k\le a$ |
| 4 | $p^4$ | $(0,1)$ | $k>a$ |
All of $k=0,\dots,3$ are handled by “$y=1$, let $x$ vary.” The smallness of $b$ only means fewer pairs use the second rule, but $x$ alone covers all divisors up to $p^a$. Total: $(a+1)+b=4+1=5=d(p^4)$.
Summary: what makes the bijection work
Three ingredients combine:
Coprimality forces exclusivity. For each prime, the power goes entirely to $x$ or entirely to $y$. This prevents any divisor from being represented twice.
The offset rule creates asymmetry. Powers assigned to $y$ are shifted up by $a=v_p(i)$, so even numerically identical exponents in $x$ and $y$ map to different divisors.
The ranges partition $\{0,\dots,a+b\}$. $x$ covers $\{0,\dots,a\}$ (size $a+1$) and $y$ covers $\{a+1,\dots,a+b\}$ (size $b$), giving $a+b+1=d(p^{a+b})$ total.
These three points, applied independently to each prime and glued together by multiplicativity, yield the identity.