Berechnung einer Summe mit Eulers Totientenfunktion

Question

Wenn $S(a,b)= \{ k \in \mathbb{Z} \mid a ~ (\mathrm{mod} ~ k) + b ~ (\mathrm{mod} ~ k) \ge k \}$Berechnen Sie die folgende Summe

$$\sum_{k\in S(m,n)}\varphi(k)$$ wo $\varphi$ ist Eulers Totientenfunktion.

---

Ich habe das alles bemerkt $k$ist so, dass $$\max(a,b) < k \le a + b$$ sind in $S(a,b)$.

(Noch ein nicht wichtiger Hinweis) es scheint so $$k \in S(n,n) \iff n ~ (\mathrm{mod} ~ k) \ge \left\lfloor \frac{n}{2} \right\rfloor$$

Ich habe jedoch immer noch keine Möglichkeit gefunden, das Problem tatsächlich zu lösen. Deine Hilfe wird geschätzt.

Answer 1

Das ist ein schönes kleines Problem. Wir brauchen nicht viel, um es zu lösen, nur die bekannte Tatsache, dass$\sum\limits_{k|n}\varphi(k)=n$und ein kleiner Einblick.

Offenbar, $S(a,b)$ist kompliziert und lässt sich nicht leicht beschreiben. Aber das brauchen wir nicht wirklich. Mal sehen wie es geht$S(a,b)$ anders als $S(a,b-1)$.

Was passiert, wenn wir hinzufügen? $1$zum (zweiten) Argument? Gut,$b\pmod k$ entweder erhöht sich um $1$ oder fällt auf $0$, es hängt davon ab $k$. Infolgedessen verschwinden einige Zahlen aus dem Satz, und einige andere Zahlen schließen sich ihm an, und der Rest bleibt dort, wo sie waren.

• Welche Zahlen verschwinden aus dem Set? Es sind genau die, für die$b\pmod k=0$das heißt, die Teiler des Neuen $b$^† .
• Was sind die Zahlen, die dem Set beitreten? Es sind diejenigen, für die$a\pmod k + b\pmod k$ war genau $1$ knapp an $k$vor dem Anstieg. Mit anderen Worten, nach dem Anstieg haben wir$a\pmod k + b\pmod k = k$, was bedeutet $(a+b)\pmod k =0$, was die Teiler von bedeutet $a+b$^† .

---

† Technisch gesehen $k$ die auch Teiler von sind $a$(falls vorhanden) muss aus beiden Sätzen ausgeschlossen werden, aber das ist nicht wichtig. Wir können sie genauso gut als eingeschlossen betrachten, da sie sich am Ende aufheben werden.

Nennen wir die fragliche Summe $Sum(a,b)$. Zusammen mit der zuvor erwähnten Tatsache haben wir$Sum(a,b)-Sum(a,b-1) = \sum\limits_{k|a+b}\varphi(k) - \sum\limits_{k|b}\varphi(k) = a+b-b = a$. Zusammen mit dem Offensichtlichen$S(a,0)=\emptyset\iff Sum(a,0)=0$ Wir haben das Endergebnis: $$Sum(a,b) = a\cdot b$$

So geht es.