OliForum Matematico

Visto che ormai mi sto HiTLeuLeRizzando, sommergero' questa sezione del forum con problemi inutili di TdN...

Si prenda un generico $ n $ intero positivo.

Sia $ X_n $ l'insieme delle quaterne di interi positivi $ (a,b,c,d) $ tali che:

1) $ a\le b\le n $

2) $ c\le d\le n $

3) $ b+d>n $

4) $ bc-ad=1 $


Dimostrare che:

$ \displaystyle |X_n|+1=\sum_{i=1}^n \varphi(i) $

Pace all'anima di Hitleuler e dei suoi criceti.

Se la condizione d) è soddisfatta, ovviamente a,b sono coprimi.
Siano $ ~ 1 \le a \le b \le n $ con a,b coprimi.
Allora, per l'algoritmo euclideo, esistono due interi c,d coprimi tali che $ ~ bc-ad=1 $. Ora, consideriamo l'insieme dei c,d che soddisfano quest'ultima condizione. Se (c,d) e (c',d') sono soluzioni, allora, semplicemente facendo la differenza, otteniamo $ ~ b(c-c') = a(d-d') $. Poichè a,b sono coprimi, avremo che c-c' è un multiplo di a e d-d' un multiplo di b.
Concludiamo che data una soluzione (c,d), tutte e sole le altre soluzioni sono date da (c+ka,d+kb) con k intero.

Ora, aggiungendo ka di qua e kb di la, certamente troviamo una soluzione in cui c,d sono positivi. Se c,d sono positivi, allora dal fatto che $ ~ bc - ad = 1 $ e $ ~ b \ge a $, tranne casi stupidi che ci daranno il -1 nella formula finale, avremo che $ ~ c \le d $.
Quindi, perchè (a,b,c,d) sia valida, ci manca solo la condizione $ ~ n-b < d \le n $, che ci conclude contemporaneamente le condizioni 2) e 3). Ma poichè le soluzioni d vanno avanti "di b in b", è ovvio che ci sarà un unico d che cade in quell'intervallino.

Quindi le quaterne (a,b,c,d) sono in corrispondenza biunivoca con le coppie (a,b) che soddisfano $ ~ 1 \le a \le b \le n $ e $ ~ (a,b) = 1 $.
E queste sono evidentemente $ ~ \sum_{i=1}^n \phi(i) $ per stessa definizione di phi.

Il + 1 uscirà da qualche strano buco

Il +1 esce perche quando b=1, e' un po difficile fare la coppia...

Cmq ok per il proof.

Btw, prova a scrivere le frazioni con $ 1\le numeratore\le denominatore\le n $ e (numeratore,denominatore)=1 in ordine crescente. Quanto fa la differenza tra due termini successivi?

E' una nota proprietà della sequenza di Farey che $ ~ \frac ab - \frac cd = \frac{1}{bd} $ se a/b, c/d sono consecutivi, però non mi è chiaro che collegamento vuoi fare col problema.

se a/b e c/d sono frazioni consecutive della serie di farey allora bc-ad=1, quindi si tratta solo di contare quante sono queste frazioni! Very nice piever

Potresti spiegare meglio?
In particolare non capisco come infili l'ipotesi b+d>n.