Zadania z funkcją Eulera

[patricia__88]

1. Jaka funkcja \(\displaystyle{ g(n)}\) dla naturalnego \(\displaystyle{ n}\) spełnia rekurencję:
\(\displaystyle{ \sum_{d|n}g(d)\varphi\left(\frac{n}{d}\right)=1}\)


2. Przyjmijmy, że \(\displaystyle{ S(m,n)}\) jest zbiorem wszystkich liczb całkowitych \(\displaystyle{ k}\) takich, że
\(\displaystyle{ m \pmod{k} +n\pmod{k} \ge k.}\)
Na przykład: \(\displaystyle{ S(7,9)=\{2,4,5,8,10,11,12,13,14,15,16\}}\).
Udowodnij, że \(\displaystyle{ \sum_{k\in S(m,n)}\varphi(k)=mn}\).
Wskazówka: pokaż, że \(\displaystyle{ \sum_{1 \le m \le n}\sum_{d|m}\varphi(d)=\sum_{d \ge 1}\varphi(d)\left \lfloor \frac{n}{d}\right \rfloor}\), a następnie rozważ \(\displaystyle{ \left \lfloor \frac{m+n}{d}\right \rfloor -\left \lfloor \frac{m}{d}\right \rfloor-\left \lfloor \frac{n}{d}\right \rfloor}\).