longlong123 wrote: Let $a$ and $b$ be positive integers such that $1\leq a<b\leq 100$. If there exists a positive integer $k$ such that $ab|a^k+b^k$, we say that the pair $(a, b)$ is good. Determine the number of good pairs. So, $(a,b)$ is good if and only if $a,b$ have the same set of prime factors.

Clearly $(a,b)=(s,s)$ with $k=2$ is a good pair. So there are 100 good pairs when $a=b$. Next assume $(a,b)$ is a good pair where $a \neq b$. Then $ab > a + b$, implying $k > 1$. Let $d=(a,b)$. Hence there exist coprime natural numbers $r$ and $s$ such that $a=rd$ and $b=sd$. Moreover we may assume $(r,d)=1$ since $a$ and $b$ are symmetric in $\frac{a^k+b^k}{ab}$. Concequently $ab \mid a^k + b^k$ $\Rightarrow \; rsd^2 \mid d^k(r^k + s^k)$ $\Rightarrow \; rs \mid d^{k-2}(r^k + s^k) \; (1)$ $\Rightarrow \; r \mid d^{k-2}(r^k + s^k)$ $\Rightarrow \; r \mid r^k + s^k$ since $(r,d)=1$ $\Rightarrow \; r \mid s^k$ $\Rightarrow \; r = 1$ since $(r,s)=1$ $\Rightarrow \; s \mid d^{k-2}(1 + s^k)$ by (1) $\Rightarrow \; s \mid d^{k-2}$ $\Rightarrow \; s = d^i$ where $2 \leq i \leq k-2$ So $(a,b) = (rd,sd) = (d,d^n)$ where $2 \leq n \leq k-1$, which are good pairs since $\frac{a^k+b^k}{ab} = \frac{d^k+d^{nk}}{d^{n+1}} = \frac{d^k+d^{nk}}{d^{n+1}}$ is an integer because $n < k$. Obviously $2 \leq d^n \leq 100$ since $a \neq b$ and $a,b \leq 100$, implying $2 \leq d \leq \sqrt[n]{100}$. Hence $2 \leq n \leq 6$. This combined with the fact $(b,a) = (d^n,d)$ is also a good pair give us the number $N$ of good pairs $(a,b)$ with $1 \leq a,b \leq 100$: $N = 100 + 2\sum_{n=2}^6 [\sqrt[n]{100}] - 1 = 100 + 2(9 + 3 + 2 + 1 + 1) = 132.$

Solar Plexsus wrote: $N = 100 + 2\sum_{n=2}^6 [\sqrt[n]{100}] - 1 = 100 + 2(9 + 3 + 2 + 1 + 1) = 132.$ But why I found the answer $96$?

skyletter wrote: Solar Plexsus wrote: $N = 100 + 2\sum_{n=2}^6 [\sqrt[n]{100}] - 1 = 100 + 2(9 + 3 + 2 + 1 + 1) = 132.$ But why I found the answer $96$? There are already $100$ good pairs $(n,n)$ with $1\leq n\leq100$

Okay, here is the official solution I believe. The answer should be 96.

Attachments:

CantonMathGuy wrote: skyletter wrote: Solar Plexsus wrote: $N = 100 + 2\sum_{n=2}^6 [\sqrt[n]{100}] - 1 = 100 + 2(9 + 3 + 2 + 1 + 1) = 132.$ But why I found the answer $96$? There are already $100$ good pairs $(n,n)$ with $1\leq n\leq100$ "$1 \leq a < b \leq 100$"