Part of solution: Let $p$ -prime odd divisor of $k$ and $n=p^t$ for some $t$. Then $v_p(a^n+b^n)=v_p(n)+v_p(a+b)>v_p(n) $ so $n|a^n+b^n$ So $S_k$ can be finite only for $k=2^t$

We claim that $S_k$ is finite only when $k$ is a power of $2$. Assume for the sake of contradiction that $k$ has an odd prime divisor, say $p$. Take $n=p^{\ell}$ for some $\ell\ge 0$. Using the Lifting the Exponent Lemma, we obtain $$\upsilon_p{(a^n+b^n)}=\upsilon_p{(a^{p^{\ell}}+b^{p^{\ell}})}=\upsilon_p{(a+b)}+\upsilon_p(n)=\upsilon_p(k)+\ell\ge 1+\ell.$$Thus we have $n|a^n+b^n$ which means that $(p^\ell,a,b)\in S_k$. Hence $S_k$ is infinite whenever $k$ has an odd divisor. Now we claim that for $k=2^{m},$ the set $S_k$ is finite. For a given $n>1$, since $n$ is odd, let $p$ be the smallest odd prime divisor of $n$. If $p$ divides $b$ then $p$ also divides $a$ contradicting the fact that $\gcd{(a,b)}=1.$ So there exists $c$ such that $bc\equiv{1}\pmod{p}$ since $\gcd{(b,p)}=1.$ We have $$a^n+b^n\equiv 0\pmod{p}\implies (ac)^n\equiv -1 \pmod{p}.$$Let $d=\text{ord}_p(ac)$, then we have $d|2n$ and $d|\varphi(p)=p-1$ giving us $d|\gcd{(2n,p-1)}\implies d\in\{1,2\}$. Case 1: $d=1$. Then we have $-1\equiv (ac)^n\equiv 1\pmod{p}\implies p=2$ a contradiction. Case 2: $d=2$. Then we have $ac\equiv 1\pmod{p}\implies p|a+b=k$ contradicting the fact that $k$ is a power of $2$. Hence we must have $n=1$ which means that $S_k$ is finite, as desired.

The only values of $k$ that yield $|S_k|<\infty$ are the powers of two. Suppose $k>1$ and $k \ne 2^m$ for any $m \ge 1$ then we can find an odd prime $r \mid k$. Now pick $a=1, b=(k-1)$ then $r \mid a^r+b^r$. Define the sequence $r_0, r_1, \dots$ as $r_0=r$ and $$r_i=\frac{a^{r_{i-1}}+b^{r_{i-1}}}{2^{v_2(a^{r_{i-1}}+b^{r_{i-1}})}}$$for all $i>0$. Now $r_0, r_1 \dots$ are odd numbers and $\tfrac{r_i}{r_{i-1}}$ is an integer by induction on $i \ge 0$. Finally, we show $r_i>r_{i-1}$, else $1+(k-1)^r=2^sr$ where $r=r_{i-1}$ and $s=v_2(k-1)$, which fails due to size issues. Alternatively, note that $$v_r(a^{r^j}+b^{r^j})=v_r(a+b)+v_r(r^j)>j$$by lifting the exponent lemma; (since $r \mid k$), so $(r^j, 1, (k-1)) \in S_k$ for all $j>0$. Now we show $k=2^m$ yields no valid triplet. Indeed suppose $n>1$ (*) is an odd number with $n \mid a^n+b^n$ for $(a,b)=1$ with $a+b=2^m$. Then $n$ is coprime to both $a,b$ so write $b \equiv ax \pmod{n}$. Then $n \mid 1+x^n$ while $2^m \equiv a(1+x) \pmod{n}$ so $(n, 1+x)=1$. Pick the smallest prime $p \mid n$ then $(p-1, n)=1$ else we contradict minimality of $p$. Now $x^{2n} \equiv 1$ and $x^{p-1} \equiv 1$ mod $p$ so $x^{\gcd(2n, p-1)} \equiv 1 \pmod{p}$ so $x^2 \equiv 1 \pmod{p}$. Thus, $p \nmid 1+x \implies p \mid x-1 \implies p \mid (1)^n+1$ which is false!

Here is my solution. Claim $k=2^m$ only works. Proof For other $k$, Just choosing a prime $p$ dividing $k$, And choosing $n=p^c$, We get $v_p{(a^{p^c}+b^{p^c})}=v_p{(a+b)}+v_p{(p^c)}\geq 1+c$ $\implies n|a^n+b^n$ Thus we get infinitely many values of triples by changing $c$. Now for $k=2^m$, $a=2^m-2l$ $b=2l$ Since $(a,b)=1$,we choose minimal prime dividing $n$,such that $n|a^n+b^n$ $p\nmid a$ and $p\nmid b$ $\implies 2^n((2^{m-1}-l)^n+l^n)\equiv 0\pmod{p}$ $\implies (2^{m-1}-l)^n\equiv -l^n\pmod{p}$ Now clearly $l^{-1}$ exists. So $x^n\equiv \frac{(2^{m-1}-l)^n}{l^n}\equiv -1\pmod{p}$ $\implies x^{2n}\equiv 1\pmod{p}$ Combining this with $F.L.T$ $\implies x^{gcd(2n,p-1)}\equiv 1\pmod{p}$ $\implies x^2\equiv 1\pmod{p}$ From here its trivial to get a contradiction.$\square$

Here's my solution: The answer is $k=2^s$ for some positive integer $s$. WLOG assume that $a<b$. We divide the proof into two parts. Proof that powers of two work Let $p$ be the smallest odd prime divisor of $n$ for some $n>1$. Then $$p \mid a_n+b^n \Rightarrow a^n \equiv -b^n \pmod{p} \Rightarrow (ab^{-1})^{2n} \equiv 1 \pmod{p} \Rightarrow o_p(ab^{-1}) \mid 2n$$However, $o_p(ab^{-1}) \mid p-1$, which gives that $o_p(ab^{-1}) \mid 2$ (as $\gcd(p-1,2n)=2$). Using the given problem condition, we get that $o_p(ab^{-1})=2$. Thus, $$ab^{-1} \equiv -1 \pmod{p} \Rightarrow p \mid a+b=k \Rightarrow p \mid 2^s \rightarrow \text{CONTRADICTION}$$Thus, if $k$ is a power of two, then only $n=1$ works. Proof that other values do not work First consider $k>3$. We show that in fact there are infinitely many solutions to $n \mid b^n+1$ if $b+1$ is not a power of two. Let $p$ be an odd prime divisor of $b+1$. Our proof depends upon the fact that if $n \mid b^n+1$, then $nq \mid b^{nq}+1$, where $q$ is an odd prime satisfying $q \mid b^n+1$ and $\gcd(q,n)=1$ (easy to prove). To use this fact, we first recursively construct an infinite sequence of distinct odd primes (with $p_1=p$) such that both $p_1p_2 \dots p_m$ and $p_{m+1}$ divide $b^{p_1p_2 \dots p_m}+1$. Such a sequence exists by Zsigmondy's Theorem. Now we're done by the previous observation. The only case left is $k=3$, which gives $a=1,b=2$. For this take $n=3^m$. Then it is easy to show that $3^m \mid 2^{3^m}+1$. Hence, done. $\blacksquare$ REMARK: The first part of my solution can be found by anyone who is familiar with orders. As for the second part, I was fortunate enough that I had solved USA TSTST 2018 P8 earlier, and so I immediately got the solution (and the answer ). P.S. Just a doubt for the seniors. Are we allowed to use Zsigmondy during the TST's?

Ankoganit wrote: For a natural number $k>1$, define $S_k$ to be the set of all triplets $(n,a,b)$ of natural numbers, with $n$ odd and $\gcd (a,b)=1$, such that $a+b=k$ and $n$ divides $a^n+b^n$. Find all values of $k$ for which $S_k$ is finite. We claim that $S_k$ is finite if and only if $k$ is a power of $2.$ First, we show $S_k$ is infinite when an odd prime $p$ divides $k.$ Suppose $p \mid k$ with $p$ odd. We claim that $(n,a,b)=(p^{\ell},1,k-1) \in S_k$ for all $\ell.$ Indeed, by LTE, noting that $n$ is odd $$\nu_p(1^{p^{\ell}}+(k-1)^{p^{\ell}})=\nu_p(1+(k-1))+\nu_p(p^{\ell}) \geqslant \ell+1$$and so $n=p^{\ell}$ divides $a^n+b^n.$ Since $\ell$ can be arbitrary, hence $S_k$ is infinite. Suppose $k$ is a power of $2.$ Assume that $S_k$ is infinite. In particular, we find an odd value of $n>1.$ Take the smallest prime factor $p$ of $n.$ Clearly, $p \nmid a$ else $p \mid a,b$ and so $p \mid k,$ which is absurd since $k$ is a power of $2.$ Now, $$a^n \equiv -b^n \implies (a \cdot b^{-1})^n \equiv -1 \pmod{p}.$$Hence, $(a \cdot b^{-1})^{(2n,p-1)} \equiv 1 \pmod{p}.$ However, if an odd prime $q \mid (2n,p-1),$ then $q \mid 2n, q \leqslant p-1.$ So $q \mid n$ with $q<p,$ contradicting minimality. Hence $(2n,p-1)=2$ as $n,p$ are odd. But then $p \mid a^2-b^2=k(a-b).$ Since $(p,k)=1,$ hence $p \mid a-b.$ However then $p \mid a^n+b^n \equiv 2 \cdot a^n \implies p \mid a,$ absurd. $\square$

Wizard_32 wrote: Ankoganit wrote: For a natural number $k>1$, define $S_k$ to be the set of all triplets $(n,a,b)$ of natural numbers, with $n$ odd and $\gcd (a,b)=1$, such that $a+b=k$ and $n$ divides $a^n+b^n$. Find all values of $k$ for which $S_k$ is finite. We claim that $S_k$ is finite if and only if $k$ is a power of $2.$ First, we show $S_k$ is infinite when an odd prime $p$ divides $k.$ Suppose $p \mid k$ with $p$ odd. We claim that $(n,a,b)=(p^{\ell},1,k-1) \in S_k$ for all $\ell.$ Indeed, by LTE, noting that $n$ is odd $$\nu_p(1^{p^{\ell}}+(k-1)^{p^{\ell}})=\nu_p(1+(k-1))+\nu_p(p^{\ell}) \geqslant \ell+1$$and so $n=p^{\ell}$ divides $a^n+b^n.$ Since $\ell$ can be arbitrary, hence $S_k$ is infinite. Suppose $k$ is a power of $2.$ Assume that $S_k$ is infinite. In particular, we find an odd value of $n>1.$ Take the smallest prime factor $p$ of $n.$ Clearly, $p \nmid a$ else $p \mid a,b$ and so $p \mid k,$ which is absurd since $k$ is a power of $2.$ Now, $$a^n \equiv -b^n \implies (a \cdot b^{-1})^n \equiv -1 \pmod{p}.$$Hence, $(a \cdot b^{-1})^{(2n,p-1)} \equiv 1 \pmod{p}.$ However, if an odd prime $q \mid (2n,p-1),$ then $q \mid 2n, q \leqslant p-1.$ So $q \mid n$ with $q<p,$ contradicting minimality. Hence $(2n,p-1)=2$ as $n,p$ are odd. But then $p \mid a^2-b^2=k(a-b).$ Since $(p,k)=1,$ hence $p \mid a-b.$ However then $p \mid a^n+b^n \equiv 2 \cdot a^n \implies p \mid a,$ absurd. $\square$ I have done it in the same way..

If $k$ has an odd factor ,namely $p$, Then we can find infinitely many $n$ ,namely powers of $p$. This can be easily verified via LTE as $n$ is odd. Now, if $a+b$ is a power of$2$,then just consider the smallest prime factor of $n$ and by an order argument we get that it divides $a+b$ which is a contradiction as $n$ has only odd prime factors.

If $k$ has an odd prime factor $p$ , then LTE gives that for any $n=p^m, n|a^n+b^n$. So , let $k=2^x$.Then considering the smallest prime factor $p$ of $n$, then $ord_p(a.b^{-1})|gcd(2n,p-1)\in \{1,2\}$.If gcd is $1$ , then of course $p$ divides $2$ , contra. Otherwise, order is $2$ and , $$p|(a.b^{-1})+1 \implies p|a+b=2^x \implies p=2$$Contra .So $n=1$ is only possibily here. So the answer is all perfect powers of $2$

Perfect for a P1

For $S_k$ being a finite set, $\boxed{k=2^m}$ is the only value for $k$. FTSOC, assume $k$ has an odd prime factor $p$ such that $v_p(n)\geq 1$. By LTE, $v_p(a^n+b^n)\geq v_p(n)+1\implies n\vert a^n+b^n$ which leads to $S_k$ being an infinite set. So, we have $a+b=k=2^m$. Now, pick the smallest prime divisor $q$ of $n$. So, $a^n+b^n\equiv 0\pmod q$ and $(2^m-b)^n+b^n\equiv 0\pmod q\implies (2^m\cdot b^{-1}-1)^{2n}\equiv 1\pmod q$. Hence, $\text{ord}_q(2^m\cdot b^{-1}-1)\vert \gcd(2n, q-1)=2$. So, the order can be either $2$ or $1$. The latter contradicts either of the facts that $\text{gcd}(a, b)=1$ or $q$ is an odd prime. Hence, $\text{ord}_q(2^m\cdot b^{-1}-1)=2$ which implies $2^m\cdot b^{-1}\equiv 2\pmod q$ but $0\equiv (2^m\cdot b^{-1}-1)+1\equiv 2\pmod q$ which creates a contradiction. Hence, $n=1$ which ensures that $S_k$ is finite. $\blacksquare$

Only powers of $2$ work. Otherwise, say $p | k$ for some odd prime $p$ and consider $a = 1, b = k-1$ and $n = p^z$. By LTE, we have that $v_p((k-1)^{p^z} + 1) = v_p(k) + v_p(p^z) \ge z+1 > z$ so $n = p^z$ divides this. If $k$ was a power of $2$, then let $d$ be the order of $\frac{b}{a} \pmod{p}$ for the smallest prime $p$ dividing $n$. Since $\frac{b^n}{a^n} \equiv -1 \pmod{p}$, we have that $d | p-1, d \nmid n, d | 2n$, and since $p$ is the smallest prime dividing $n$, this forces that $d = 2$, so $p | a+b$, impossible since $a+b = k$ is a power of $2$. $\blacksquare$

handwritten solution images attached

For $k$ not a power of $2$, $a+b=k \implies$ there exists an odd prime $p|k$, so $p|a+b$, since $\gcd(a,b)=1$, $p \nmid a, b$ so for $n=p^e$ we have by LTE $\nu_p(a^{p^e}+b^{p^e})=\nu_p(a+b)+\nu_p(p^e)>\nu_p(p^e)$ so $p^e|a^{p^e}+b^{p^e}$ for all $e$. Thus we can generate an infinite amount of triples by iterating $n$ through $\{p, p^2, \ldots \}$. For $k$ a power of $2$, $a+b=k=2^t$ means that for any odd $n$, $n \nmid a+b$. Since $a+b \mid a^n+b^n$, we must have $n \mid \frac{a^n+b^n}{a+b}$. That means for the smallest odd prime $p \mid n$. $p \mid a^n+b^n$ but $p \nmid a+b$. So $a^n+b^n \equiv 0 \mod{p} \implies (-\frac{a}{b})^n \equiv 1 \mod{p}$, but since $\gcd(n, p-1)=1$ as $n$ is odd, the order must be $1$. So $-\frac{a}{b} \equiv 1 \mod{p} \implies a \equiv -b \mod{p} \implies a+b \equiv 0 \mod{p}$ which is absurd. Thus $n$ has no odd prime factors so $n=1$ is the only possible solution, that means $S_k$ is finite as there are only finitely partitions of $k$.

Our answer is when $k$ is a power of 2. Suppose, FTSOC, an odd prime $p \mid k$. Take $n = p^{\alpha}$, and since $p \mid a + b$, we may use LTE. $v_p(a^n + b^n) = v_p(a + b) + v_p(n) \geq v_p(n)$, and since $p$ is the only divisor of $n$, our condition is satisfied. So, take $n$ to be any perfect power of $p$, giving an infinite set. Therefore, $k$ must be a power of $2$. Let $q$ be the smallest prime divisor of $n$. We have: \[ q \mid a^n +\ b^n \implies a^n \equiv - b^n \pmod{q} \implies \left(\frac{a}{b}\right)^{n} \equiv 1 \pmod{q} \implies \left(\frac{a}{b}\right)^{2n} \equiv 1 \pmod{q} \]So, $\text{ord}_q\left(\frac{a}{b}\right) \mid 2n$, and since $\left(\frac{a}{b}\right)^{q - 1} \equiv 1\mod{q}$, $\text{ord}_q\left(\frac{a}{b}\right) \mid (2n, q - 1) = 2(n, q - 1)$. Notice $(n, q - 1) = 1$, since $q$ is the smallest prime divisor of $n$, so $\text{ord}_q\left(\frac{a}{b}\right) \mid 2$, and $\text{ord}_q\left(\frac{a}{b}\right) = 2 \implies a \equiv -b \mod{q} \implies q \mid a + b$, however this is a power of 2, a clear contradiction, as then $n$ is even.