Sunday 24 January 2021

What set is larger

Which set is larger for a given number c

  • All unordered distinct pairs of natural numbers (a, b) such that c = lcm(a, b)

  • All unordered distinct pairs of natural number (a, b) such that 1/a + 1/b = 1/c

I claim that both these sets are equal to the number of unordered distinct pairs (x, y) such that xy = c2

Do proof this, we just have to find two bijections that project x,y on a,b such that both expression are equivalant.

Least common multiple

See this injection
$$\left\{ \begin{matrix}a = \gcd(x,\sqrt{xy})\\b = \gcd(y,\sqrt{xy})\end{matrix}\right. \Leftrightarrow \left\{ \begin{matrix}x=a^2/\gcd(a,b)\\y=b^2/\gcd(a,b)\end{matrix}\right. $$

We know have to proof 2 things. First that this is actually consistent, and secondly that it projects the right sets onto each other.

Consistency

Let us plug in the equations on the right, into the equations on the left
$$\begin{aligned} a' &= \gcd(x,\sqrt{xy})\\ &= \gcd(a^2/\gcd(a,b),\sqrt{a^2/\gcd(a,b)b^2/\gcd(a,b)})\\ &= \gcd(a^2/\gcd(a,b),ab/\gcd(a,b))\\ &= \frac{a}{\gcd(a,b)} \gcd(a,b)\\ &= a \end{aligned} $$

Analog for b.

Closed (left)

If
xy = c2

Then is
$$\begin{aligned} \gcd(x,y) &| x\\ \gcd(x,y) &| y\\ \gcd(x,y)^2 &| xy\\ \gcd(x,y)^2 &| c^2\\ \gcd(x,y) &| c\\ xy/c &|xy/\gcd(x,y) \\ c &|\text{lcm}(x,y) \end{aligned}$$
Thus


$$\begin{aligned} \text{lcm}(a,b) &= \text{lcm}(\gcd(x,\sqrt{xy}),\gcd(y,\sqrt{xy}))\\ &= \gcd(\sqrt{xy},\text{lcm}(x,y))\\ &= c \end{aligned}$$

Closed (right)

If
c = lcm(a, b)

Then


$$\begin{aligned} xy &= a^2/\gcd(a,b) \times b^2/\gcd(a,b)\\ &= \text{lcm}(a,b)^2\\ &= c^2 \end{aligned}$$

Sum of fractions

See this injection
$$\left\{ \begin{matrix}a = x+c\\b = y+c\end{matrix}\right. \Leftrightarrow \left\{ \begin{matrix}x=a-c\\y=b-c\end{matrix}\right. $$

The consistency of this injection is trivial.

That this is closed can be proved as follows:


$$\begin{aligned} \frac{1}{x+c} + \frac{1}{y+c} &= \frac{1}{c}\\ \frac{x+c+y+c}{(x+c)(y+c)} &= \frac{1}{c}\\ \frac{x+y+2c}{xy+xc+yc+c^2} &= \frac{1}{c}\\ xc+yc+2c^2 &= xy+xc+yc+c^2\\ c^2 &= xy\\ \end{aligned}$$