# Solution Multiplicity of the Diophantine Equation $k = b(a - \gcd(a,b))$.

Let $f(k) = | \{ (a,b) \in \mathbb{N}^{2} \, | \, k = b(a- \gcd(a,b)) \}|$. It is clear that $f(0)$ is infinite since one may take any $b \in \mathbb{N}$ and any divisor of $b$ as $a$. From numerical experiments, however, it appears that $f(k) = 1$ if and only if $k \in \{1,2,6, 42,1806 \}$, so $f(k) = 1$ is finite. What of $f(k) = n$ for some $n \in \mathbb{N}_{>1}$ and $k \in \mathbb{N}$? Is it infinite or finite as a function of $n$?

I conjecture that the number of $k$ satisfying $f(k) = n$ is finite for $n \in \mathbb{N}$, and for each $k \in \mathbb{N}$, $f(k)$ is finite.

For example, computer experiments show that $f(57600) \geqslant 226$, while $\tau(57600) = 81$, as the following pairs (not a complete list) solve the equation $57600 = b(a-\gcd(a,b))$: \begin{array}{cc} 22 & 2880 \\ 25 & 2880 \\ 26 & 2400 \\ 27 & 2400 \\ 28 & 2400 \\ 31 & 1920 \\ 33 & 1920 \\ 34 & 1800 \\ 35 & 1920 \\ 36 & 2400 \\ 37 & 1600 \\ 38 & 1600 \\ 41 & 1440 \\ 44 & 1440 \\ 45 & 1920 \\ 49 & 1200 \\ 50 & 1440 \\ 51 & 1200 \\ 52 & 1200 \\ 54 & 1200 \\ 56 & 1200 \\ 61 & 960 \\ 62 & 960 \\ 63 & 960 \\ 64 & 1200 \\ 65 & 960 \\ 66 & 960 \\ 68 & 900 \\ 70 & 960 \\ 72 & 1200 \\ 73 & 800 \\ 74 & 800 \\ 75 & 960 \\ 76 & 800 \\ 82 & 720 \\ 85 & 720 \\ 88 & 720 \\ 90 & 960 \\ 91 & 640 \\ 95 & 640 \\ 96 & 1200 \\ 97 & 600 \\ 98 & 600 \\ 99 & 600 \\ 100 & 720 \\ 101 & 576 \\ 102 & 600 \\ 104 & 600 \\ 108 & 600 \\ 121 & 480 \\ 122 & 480 \\ 123 & 480 \\ 124 & 480 \\ 125 & 480 \\ 126 & 480 \\ 130 & 480 \\ 132 & 480 \\ 135 & 480 \\ 140 & 480 \\ 146 & 400 \\ 148 & 400 \\ 150 & 480 \\ 151 & 384 \\ 152 & 400 \\ 153 & 384 \\ 160 & 720 \\ 161 & 360 \\ 164 & 360 \\ 170 & 360 \\ 180 & 480 \\ 181 & 320 \\ 182 & 320 \\ 185 & 320 \\ 190 & 320 \\ 193 & 300 \\ 194 & 300 \\ 196 & 300 \\ 198 & 300 \\ 200 & 360 \\ 202 & 288 \\ 204 & 300 \\ 241 & 240 \\ 242 & 240 \\ 243 & 240 \\ 244 & 240 \\ 245 & 240 \\ 246 & 240 \\ 248 & 240 \\ 250 & 240 \\ 252 & 240 \\ 255 & 240 \\ 256 & 240 \\ 257 & 225 \\ 260 & 240 \\ 264 & 240 \\ 270 & 240 \\ 280 & 240 \\ 288 & 240 \\ 289 & 200 \\ 292 & 200 \\ 296 & 200 \\ 300 & 240 \\ 301 & 192 \\ 302 & 192 \\ 303 & 192 \\ 306 & 192 \\ 320 & 240 \\ 322 & 180 \\ 325 & 180 \\ 340 & 180 \\ 360 & 240 \\ 361 & 160 \\ 362 & 160 \\ 364 & 160 \\ 365 & 160 \\ 370 & 160 \\ 380 & 160 \\ 386 & 150 \\ 387 & 150 \\ 401 & 144 \\ 404 & 144 \\ 416 & 144 \\ 451 & 128 \\ 480 & 240 \\ 481 & 120 \\ 482 & 120 \\ 483 & 120 \\ 484 & 120 \\ 485 & 120 \\ 486 & 120 \\ 488 & 120 \\ 490 & 120 \\ 492 & 120 \\ 495 & 120 \\ 500 & 120 \\ 504 & 120 \\ 510 & 120 \\ 520 & 120 \\ 540 & 120 \\ 577 & 100 \\ 578 & 100 \\ 600 & 120 \\ 601 & 96 \\ 602 & 96 \\ 603 & 96 \\ 604 & 96 \\ 606 & 96 \\ 612 & 96 \\ 641 & 90 \\ 650 & 90 \\ 721 & 80 \\ 722 & 80 \\ 724 & 80 \\ 725 & 80 \\ 728 & 80 \\ 730 & 80 \\ 736 & 80 \\ 740 & 80 \\ 760 & 80 \\ 769 & 75 \\ 771 & 75 \\ 800 & 80 \\ 802 & 72 \\ 808 & 72 \\ 901 & 64 \\ 902 & 64 \\ 961 & 60 \\ 962 & 60 \\ 963 & 60 \\ 964 & 60 \\ 965 & 60 \\ 966 & 60 \\ 970 & 60 \\ 972 & 60 \\ 975 & 60 \\ 980 & 60 \\ 990 & 60 \\ 1020 & 60 \\ 1153 & 50 \\ 1154 & 50 \\ 1201 & 48 \\ 1202 & 48 \\ 1203 & 48 \\ 1204 & 48 \\ 1206 & 48 \\ 1208 & 48 \\ 1212 & 48 \\ 1216 & 48 \\ 1224 & 48 \\ 1248 & 48 \\ 1285 & 45 \\ 1441 & 40 \\ 1442 & 40 \\ 1444 & 40 \\ 1445 & 40 \\ 1448 & 40 \\ 1450 & 40 \\ 1460 & 40 \\ 1480 & 40 \\ 1601 & 36 \\ 1604 & 36 \\ 1801 & 32 \\ 1802 & 32 \\ 1804 & 32 \\ 1921 & 30 \\ 1922 & 30 \\ 1923 & 30 \\ 1925 & 30 \\ 1926 & 30 \\ 1930 & 30 \\ 1935 & 30 \\ 1950 & 30 \\ 2401 & 24 \\ 2402 & 24 \\ 2403 & 24 \\ 2404 & 24 \\ 2406 & 24 \\ 2408 & 24 \\ 2412 & 24 \\ 2424 & 24 \\ 2881 & 20 \\ 2882 & 20 \\ 2884 & 20 \\ 2885 & 20 \\ 2890 & 20 \\ 2900 & 20 \end{array}

• I believe your list is incomplete; it's missing pairs such as $(b,a)=9600,9)$. The actual value of $f(57600)$ seems to be equal to $274$. Also, the list of $f(k)=1$ numbers seems to be missing $6$. – Peter Košinár Jan 10 '14 at 9:35

For any fixed $b$, there are only finitely many possible values of $\gcd(a,b)$; the divisors of $b$. Thus, we can let $g$ go over all divisors of $b$, calculate corresponding value of $a$ and check if $g$ is indeed equal to $\gcd(a,b)$. Expressed as a double sum, we have
$$f(k)=\sum_{b\ |\ k} \sum_{g\ |\ b} \left[\gcd\left(\frac{k}{b}+g,b\right)\stackrel{?}{=}g\right]$$ where the summed quantity is equal to $1$ if the equality is satisfied and $0$ otherwise. This proves that $f(k)$ is finite for $k\geq 1$ and provides a loose upper bound on its value.
On the other hand, let $p$ be any odd prime. Then, there are just three possible pairs of $(b,g)$: $(1,1)$, $(p,1)$ and $(p,p)$; of which precisely first two satisfy the requirements. Thus, $f(p)=2$ for all odd primes $p$, making $\{k\ |\ f(k)=2\}$ infinite. Of course, primes are not the only numbers with this property.