Calculando uma soma com a função totiente de Euler

Question

E se $S(a,b)= \{ k \in \mathbb{Z} \mid a ~ (\mathrm{mod} ~ k) + b ~ (\mathrm{mod} ~ k) \ge k \}$, calcule a seguinte soma

$$\sum_{k\in S(m,n)}\varphi(k)$$ Onde $\varphi$ é a função totiente de Euler.

---

Eu percebi que tudo $k$é tal que $$\max(a,b) < k \le a + b$$ estão dentro $S(a,b)$.

(Mais uma nota não importante), parece que $$k \in S(n,n) \iff n ~ (\mathrm{mod} ~ k) \ge \left\lfloor \frac{n}{2} \right\rfloor$$

No entanto, ainda não descobri nenhuma maneira de realmente resolver o problema. Agradecemos sua ajuda.

Answer 1

Agora, esse é um pequeno problema bom. Não precisamos de muito para resolver isso, apenas o fato de que$\sum\limits_{k|n}\varphi(k)=n$e um pouco de visão.

Pelo visto, $S(a,b)$é complicado e não será descrito facilmente. Mas realmente não precisamos disso. Vamos ver como é$S(a,b)$ diferente de $S(a,b-1)$.

O que acontece quando adicionamos $1$para o (segundo) argumento? Bem,$b\pmod k$ ou aumenta em $1$ ou cai para $0$, dependendo $k$. Consequentemente, alguns números desaparecem do conjunto e alguns outros números se juntam a ele, e o resto permanece onde estava.

• Quais são os números que desaparecem do conjunto? São exatamente aqueles para os quais$b\pmod k=0$, isto é, os divisores do novo $b$^† .
• Quais são os números que unem o conjunto? São aqueles para os quais$a\pmod k + b\pmod k$ foi exatamente $1$ com falta de $k$antes do aumento. Em outras palavras, após o aumento temos$a\pmod k + b\pmod k = k$, que significa $(a+b)\pmod k =0$, o que significa os divisores de $a+b$^† .

---

† Tecnicamente, aqueles $k$ que também são divisores de $a$(se houver) deve ser excluído de ambos os conjuntos, mas isso não é importante. Podemos muito bem considerá-los incluídos, pois eles se cancelarão no final.

Vamos chamar a soma em questão $Sum(a,b)$. Juntamente com o fato mencionado anteriormente, temos$Sum(a,b)-Sum(a,b-1) = \sum\limits_{k|a+b}\varphi(k) - \sum\limits_{k|b}\varphi(k) = a+b-b = a$. Junto com o óbvio$S(a,0)=\emptyset\iff Sum(a,0)=0$ temos o resultado final: $$Sum(a,b) = a\cdot b$$

Assim vai.