Part a) is easy For $n=2$ we can take $a=p,b=p^k$, then $\frac{a+b}{p}=p^{k-1}+1,\frac{a^2+b^2}{p^2}=1+p^{2k-1}$ For $n>2$ we have $p^2\not |a+b$ By LTE: If $p \neq 2$ then $2=v_p(a^n+b^n)=v_p(a+b)+v_p(n)=1+v_p(n)$ So $A_n$ consists only such primes $p$, that $p|n$ and $p^2 \not | n$ and maybe $p=2$

What is $f(n)$? Number of elements of $A_n$?

Yup $f(n)$ is the number of elements of $A_n$ if $A_n$ is finite in size.

Part b) Let $g_p(k)=1$ if $p|k,p^2 \not |k$ and $g_p(k)=0$ in other cases. Then $f(k)=\sum_{p|k}g_{p}(k)$ Let $p|mk$ Case 1:$deg_p(k)=0$ then $g_p(d)=0,g_p(m)-g_p(mk)=0$ Case 2: $deg_p(k)=1,g_p(k)=1$ Then possible cases: $deg_p(m)=0 \to g_p(m)=0, g_p(d)=0,g_p(mk)=1$ $deg_p(m)=1 \to g_p(m)=1, g_p(d)=1, g_p(mk)=0$ $deg_p(m)>1 \to g_p(m)=0, g_p(d)=1,g_p(mk)=0$ So for every $p$ such that $g_p(k)=1$ it is true, that $g_p(d) \leq g_p(k)+g_p(m)-g_p(mk) \leq 2g_p(d)$ Case 3:$ deg_p(k)>1,g_p(k)=0 \to g_{p}(mk)=0$ then $g_p(d)=g_p(m)$ For every $p|mk$ it is true that $g_p(d) \leq g_p(k)+g_p(m)-g_p(mk) \leq 2g_p(d)$ and we can sum for every such $p$

RagvaloD wrote: Part a) is easy For $n=2$ we can take $a=p,b=p^k$, then $\frac{a+b}{p}=p^{k-1}+1,\frac{a^2+b^2}{p^2}=1+p^{2k-1}$ For $n>2$ we have $p^2\not |a+b$ By LTE: If $p \neq 2$ then $2=v_p(a^n+b^n)=v_p(a+b)+v_p(n)=1+v_p(n)$ So $A_n$ consists only such primes $p$, that $p|n$ and $p^2 \not | n$ and maybe $p=2$ But LTE for a^n+b^n only works for odd n

@automatryr for $n = 2k , k>1$ it's easy since $a = -b (mod p) => a^n = (-b)^n (mod p) => a^n = b^n (mod p)$ and $a^n + b^n = 0(mod p) => 2a^n = 0(mod p)$ for $p>2$ , $p$ divides $a$ and hence $v_p(a^n + b^n) > 2$ which is absurd.

Oh thanks

Once you note f(k) = $\mid \{ p \mid v_p(k) = 1, 2 \nmid k \} \mid$ for odd k, the rest is casework.

RagvaloD wrote: Part a) is easy For $n=2$ we can take $a=p,b=p^k$, then $\frac{a+b}{p}=p^{k-1}+1,\frac{a^2+b^2}{p^2}=1+p^{2k-1}$ For $n>2$ we have $p^2\not |a+b$ By LTE: If $p \neq 2$ then $2=v_p(a^n+b^n)=v_p(a+b)+v_p(n)=1+v_p(n)$ So $A_n$ consists only such primes $p$, that $p|n$ and $p^2 \not | n$ and maybe $p=2$ we should not take a=p as a is relatively prime to p.

For $n\neq 2$, we see taking $a$ and $b$ both divisible by $p$ won't do us any good, so we write $a=kp-b$. Then, $(kp-b)^n+b^n \equiv nkp(-b)^{n-1}+(-b)^n+b^n (\mod p^2)$. For even $n$, we have that $b^{n-1}(nkp+2b)$ is divisible by $p^2$, which can't be the case for any $p$ since $p$ does not divide $b$. For odd $n$, we get $v_{p}(n)=1$ as a condition for $p$ to be in $A_n$, which solves part a. For part b: Let: $A$ be the number of primes that divide $m$ once and don't divide $k$, $B$ be the number of primes that divide $k$ once and don't divide $m$, $C$ be the number of primes that divide both $m$ and $k$ only once, $D$ be the number of primes that divide $m$ once and $k$ more than once, and $E$ be the number of primes that divide $k$ once and $m$ more than once. Other primes are irrelevant for $f$. We can now see that: $f(d)=C+D+E$ $f(k)=B+C+E$ $f(m)=A+C+D$ $f(km)=A+B$. Now the inequality we needed to prove is equivalent to: $C+D+E \leq 2C+D+E \leq 2C+2D+2E$, which obviously holds.

a) For $n=2$, pick a prime $p \equiv 1 \pmod{4}$. It is well known that there exist integers $m$ and $n$ such that $p = m^2 + n^2 $. Set $a = pm$ and $b = pn$. This clearly works. By Dirichlet there are infinitely many primes $p \equiv 1 \pmod{4}$, so this shows $A_2$ is infinite. For $n > 2$, suppose that $a + b = kp$. Obviously $p$ does not divide $a$ and $b$ because $\nu_p(a^2 +b^2 = 2)$. Since $a^n + b^n \equiv a^n + (-a)^n) \pmod{p}$, $n$ must be odd. \[ a^n + b^n = a^n + kp - b^n \equiv a^n - a^n + a^{n-1} p \equiv na^{n-1} \pmod{p^2} . \]Because $p$ does not divide $a$, it must divide $n$. However, this can only hold for finitely many $p$ so $A_n$ is finite. b) Define an indicator function \[ 1_p(n) = \begin{cases} 1 &\text{if $\nu_p(n)=1$,} \\ 0 &\text{otherwise.} \end{cases} \]We claim that \[ 1_p(d) \leq 1_p(k) + 1_p(m) - 1_p(km) \leq 2 \cdot1_p(d) \tag{1}.\]There are 4 cases that we look at based on $1_p(k)$ and $1_p(m)$. The general observation is that $\nu_p(km) = \nu_p(k) + \nu_p(m)$ and $\nu_p(d) = \min\{ \nu_p(k), \nu_p(m) \}$. If $1_p(k) = 1_p(m) = 0$, then $1_p(km) = 1_p(d) = 0$ since either both are divisible by $p^2$ or neither are divisible by $p$. If $1_p(k) = 1$ and $\nu_p(m) = 0$, then $1_p(km) = 1$ and $1_p(d) = 0$. If $1_p(k) = 1$ and $\nu_p(m) \geq 2$, then $1_p(km) = 0$ and $1_p(d) = 0$. If $1_p(k) = 1_p(m) = 1$, then $1_p(km) = 0$ and $1_p(km) = 1$. It is easy to verify that all four of these cases obey the bound in (1). We have already shown that $\gcd(a,p) = 1$ for all $n > 2$. Then by the Lifting the Exponent Lemma, \[ \nu_p(a^n + b^n) = \nu_p(a+b) + \nu_p(n) = 1 + \nu_p(n) \]for all odd primes. Additionally, $2$ cannot be in $A_n$ because if $\nu_2(a+b) = 1$, then \[ a \equiv b \pmod{4} \implies a^n \equiv b^n \pmod{4} \implies a^n + b^n \equiv 2 \pmod{4}. \]Thus \[ A_n = \{ p \mid \nu_p(n) = 1 \} \implies f(n) = \sum_p 1_p(n) . \]where the sum is taken over all primes. Summing the inequality in (1) over all the primes gives the desired result.

For the first part, for odd $n$ ,by LTE ,$A_{n}$ is clearly finite.Also $n$ being an even number greater than $2$ doesn't work.It can be verified that for $n=2$,there are inifintely many primes working. For,part b,I had the same solution as #14,which I believe is the cleanest solution.

a) Note that $|A_1| = 0$. Assume that $n \geq 3$ is an odd integer. It is easy to check that $2 \not \in A_n$. So assume $p$ is an odd prime that is in $A_n$. We have $v_p(a+b) = 1$ and $v_p(a^n + b^n) = 2$. Also by LTE, $2 = v_p(a^n + b^n) = v_p(a+b) + v_p(n) = 1 + v_p(n) \implies v_p(n) = 1$. Thus, $A_n$ is the set of primes that have an exponent $1$ in the prime factorization of $n$, and thus it is finite. Now, if $n = 2$, for an arbitrary prime $p \geq 7$, choose $a = 2p$ and $b = p$, so it is clear that all primes $p \geq 7$ work, so $|A_2| = \infty$. Finally, if $n \geq 4$ is an even integer, let $p \geq 3$ be a prime. Then from the first condition we get $a \equiv -b \pmod{p}$ and plugging this into the second we get $b \equiv 0 \equiv a \pmod{p}$. Thus, $v_p(a^n + b^n) \geq n \geq 4$, contradiction, so $|A_n| \leq 1$ in this case. b) Remember that when $t$ is odd, $f(t)$ is the number of primes that have exponent $1$ in the prime factorization of $t$. Let $m = dx , n = dy$ with $\text{gcd}(x,y) = 1$. If $\text{gcd}(d,x) = \text{gcd}(d,y) = 1$, then $$f(k) + f(m) - f(km) = f(dx) + f(dy) - f(d^2xy) = f(d) + f(x) + f(d) + f(y) - f(x) - f(y) = 2f(d)$$and inequalities are satisfied. Assume WLOG that $\text{gcd}(d,x) = \ell > 1$ and $\text{gcd}(d,y) = 1$. Then, $$f(k) + f(m) - f(km) = f(dx) + f(dy) - f(d^2xy) = f(dx) + f(d) - f(d^2x)$$. Now let $p$ be a prime such that $p \mid dx$ and $v_p(dx) = 1$. If $p \mid d$, then this prime is not counted in $f(d^2x)$ but is counted in $f(dx)$. If $p \mid x$, then this prime is counted in both $f(d^2x)$ and $f(dx)$. Thus, $f(dx) - f(d^2x) \geq 0$ and $f(dx) - f(d^2x) \leq f(d)$. These give the desired inequalities and we are done.

The condition is equivalent to $\nu_p(a+b) = 1, \nu_p(a^n + b^n) = 2$. Part a) If $n$ is odd, we can use LTE and get $2 = \nu_p(a^n + b^n) = \nu_p(a+b) + \nu_p(n)$, so $\nu_p(n) = 1$ if $p$ is odd. There are obviously finitely many such $p$. To see that $p=2$ fails, suppose $a+b\equiv 2\pmod 4$. Then $0\equiv a^n + b^n \equiv a+b \pmod 4$, which is impossible. If $n$ is $2$, clearly $a=b=p$ works for any prime $p$, which means $A_2$ is infinite. If $n>2$ is even and $p$ is odd, then notice that if $a\equiv b\pmod p$, then $a^n + b^n\equiv 2a^n \equiv 0\pmod p$. In this case, we have $p\mid a$ and $p\mid b$, so $\nu_p(a^n + b^n) = 2$ is impossible. Therefore we must have $p=2$, which means $A_n$ is finite. Part b) By LTE, we have that $f(n)$ is the number of odd primes $p$ with $\nu_p(n) = 1$. For each prime $p$ and positive integer $n$, let \[w_p(n) = \begin{cases} 1& \text{ if } \nu_p(n) = 1\\ 0 & \text{ if otherwise} \\ \end{cases}\]We have $f(n) = \sum w_p(n)$ (since $p=2$ fails as proved in part a). Claim: For all primes $p$, we have \[w_p(d) \le w_p(k) + w_p(m) - w_p(km) \le 2 w_p(d)\]Proof: We split into cases on $\nu_p(d)$. Case 1: $p\nmid d$. Clearly $p$ cannot divide both $k$ and $m$. If $p$ divided none of $k,m$, we would have $w_p(k) = w_p(m) = w_p(km)= 0$, which means the inequality holds true. If $p$ divided exactly one of $k,m$, WLOG $p$ divides $k$. Then $w_p(k) = w_p(km) =1, w_p(m) = 0$, so the inequality holds true. Case 2: $\nu_p(d) = 1$. We want to show that \[1\le w_p(k) + w_p(m) - w_p(km) \le 2\] Suppose this was not the case. Notice that $p$ must divide both $k$ and $m$, but $p^2$ cannot divide both $k$ and $m$. WLOG that $\nu_p(k) = 1$. The inequality becomes $0\le w_p(m) - w_p(km) \le 1$. This follows because $p\mid k$ and $p\mid m$ implies $w_p(km) = 0$, and obviously $w_p(m) \in [0,1]$. Case 3: $\nu_p(d)>1$. Then $p^2$ divides $k,m,$ and $km$, so $w_p(k) = w_p(m) = w_p(km) = 0$, so the inequality holds true. We have exhausted all cases, so the claim is true. $\square$ Summing the inequality over all primes $p$ gives the desired result.