Hallar la suma de los cuadrados de los números que son menores que $n$ y coprima a ella

Question

Hallar la suma de los cuadrados de los números que son menores que $n$ y coprima a ella. El libro escribió la respuesta:

$\frac{\phi (n)}{6}(2n^2+(-1)^m p_1p_2 \dots p_m)$

Dónde $p_1,p_2,\dots p_m$ Sólo son primos que lo dividen.Estaba en la parte del principio de inclusión-exclusión pero no entiendo cómo el principio de inclusión-exclusión puede resolver esto?

Answer 1

$$f(n) =\sum_{m \le n} m^2 = \frac{n(n+1)(2n+1)}{6}= \sum_{l=1}^3 c_l n^l, \qquad c_1= \frac16,c_2=\frac12,c_3 = \frac13$$ Mira las funciones multiplicativas $$h_l(n) = \sum_{d | n} \mu(d) d^2 (n/d)^l=\prod_{p^k \| n} h(p^k)= \prod_{p^k \| n} (p^{lk}-p^{2+l(k-1)})$$ $$h_1(n) = n \frac{\phi(n)}{n}(-1)^{\omega(n)} \prod_{p | n} p,\qquad h_2(n) = 0 (n \ne 1), \qquad h_3(n) = n^3 \frac{\phi(n)}{n}$$ Por lo tanto, $$\sum_{m \le n, (m,n)=1} m^2 =\sum_{d | n} \sum_{m \le n, d | m} m^2= \sum_{d | n} \mu(d) d^2 f(n/d)= \sum_{l=1}^3 c_l h_l(n)\\= \frac{\phi(n)}{6}(2n^2+(-1)^{\omega(n)} \prod_{p | n} p)$$

Answer 2

Suponemos que OP entiende el argumento de inclusión-exclusión utilizado para evaluar $\varphi(n).$ Utilizando el mismo procedimiento e introduciendo

$$a(n) = \sum_{k=1}^n k^2 = \frac{1}{3} n^3 + \frac{1}{2} n^2 + \frac{1}{6} n$$

y con $\mathcal{P}$ el conjunto de primos que dividen $n$ tenemos pues para la suma deseada

$$\sum_{\mathcal{Q}\subseteq\mathcal{P}} (-1)^{|\mathcal{Q}|} a\left(\frac{n}{\prod_{p\in \mathcal{Q}} p}\right) \prod_{p\in \mathcal{Q}} p^2.$$

Ahora haz los tres términos por turnos empezando por el de menor orden, que da como resultado

$$\frac{1}{6} n \sum_{\mathcal{Q}\subseteq\mathcal{P}} (-1)^{|\mathcal{Q}|} \prod_{p\in \mathcal{Q}} p = \frac{1}{6} n \prod_{p\in \mathcal{P}} (1-p) = \frac{1}{6} n \prod_{p\in \mathcal{P}} \left(\frac{1}{p}-1\right) \prod_{p\in \mathcal{P}} p \\ = \frac{1}{6}\varphi(n) (-1)^{|\mathcal{P}|} \prod_{p\in \mathcal{P}} p.$$

El siguiente plazo es

$$\frac{1}{2} n^2 \sum_{\mathcal{Q}\subseteq\mathcal{P}} (-1)^{|\mathcal{Q}|} = \frac{1}{2} \prod_{p\in \mathcal{P}} (1-1) = 0.$$

Obtenemos para el tercer y último término

$$\frac{1}{3} n^3 \sum_{\mathcal{Q}\subseteq\mathcal{P}} (-1)^{|\mathcal{Q}|} \prod_{p\in \mathcal{Q}} \frac{1}{p} = \frac{1}{3} n^3 \prod_{p\in \mathcal{P}} \left(1-\frac{1}{p}\right) = \frac{1}{3} n^2 \varphi(n).$$

Recogiendo todo lo que encontramos

$$\bbox[5px,border:2px solid #00A000]{ \frac{1}{6} \varphi(n) \left(2n^2 + (-1)^{|\mathcal{P}|} \prod_{p\in \mathcal{P}} p\right).}$$

El siguiente código de Maple puede utilizarse para explorar estas estadísticas.

with(numtheory);
with(combinat);

a := unapply(expand(sum(k^2, k=1..n)), n);

S :=
proc(n)
option remember;
local k, res;
    res := 0;

    for k to n do
        if gcd(n, k) = 1 then
            res := res + k^2;
        fi;
    od;

    res;
end;

S1 :=
proc(n)
local res, P, S, Q;
    res := 0;

    P := factorset(n);
    S := subsets(P);

    while not S\[finished\] do
        Q := S\[nextvalue\]();

        res := res +
        (-1)^nops(Q)\*a(n/mul(p, p in Q))
        \*mul(p^2, p in Q);
    end do;

    res;
end;

S2 :=
proc(n)
local P;
    P := factorset(n);
    1/6\*phi(n)\*(2\*n^2 + (-1)^nops(P)\*mul(p, p in P));
end;