Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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}

share|improve this question
    
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 at 9:35
    
Thank you, Peter! –  user02138 Jan 10 at 16:53

1 Answer 1

up vote 1 down vote accepted

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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