1
$\begingroup$

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}

$\endgroup$
  • $\begingroup$ 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$. $\endgroup$ – Peter Košinár Jan 10 '14 at 9:35
2
$\begingroup$

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.

$\endgroup$

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.