f iniettiva

Numeri interi, razionali, divisibilità, equazioni diofantee, ...
Rispondi
Avatar utente
jordan
Messaggi: 3988
Iscritto il: 02 feb 2007, 21:19
Località: Pescara
Contatta:

f iniettiva

Messaggio da jordan » 09 ott 2008, 07:32

Mostrare che la $ f(n)=\displaystyle \sum_{gcd(i,n)=1}{i} $ è iniettiva :D :D


Ps. ovviamente $ f:\mathbb{N} \to \mathbb{N} $ a scanso di equivoci
[Grazie a eli9o- fa eccezione il caso f(1)=f(2), quindi poniamo n>1 nella tesi.. :wink: ]
The only goal of science is the honor of the human spirit.

String
Messaggi: 225
Iscritto il: 01 giu 2008, 17:21

Messaggio da String » 10 ott 2008, 19:52

Se $ (i,n)=1 $ allora anche $ (n,n-i)=1 $. Il numero degli i coprimi con n è $ \phi(n) $. Avremo allora che $ \phi(n) $ è formato da coppie di numeri la cui somma è $ n $. Quindi $ \displaystyle \sum_{gcd(i,n)=1} i=\displaystyle \frac {\phi(n)\cdot n}{2} $
E qui mi sono fermato. Qualche aiutino su come continuare?
Ultima modifica di String il 10 ott 2008, 22:48, modificato 1 volta in totale.
"fatti non foste a viver come bruti,
ma per seguir virtute e canoscenza"(Dante)

Avatar utente
jordan
Messaggi: 3988
Iscritto il: 02 feb 2007, 21:19
Località: Pescara
Contatta:

Messaggio da jordan » 10 ott 2008, 21:56

Aiutino?

Mostrare che se $ a\phi(a)=b\phi(b) $ allora $ a=b $ :lol: :lol:
The only goal of science is the honor of the human spirit.

eli9o
Messaggi: 106
Iscritto il: 14 mag 2008, 19:43

Messaggio da eli9o » 11 ott 2008, 14:28

Dato che ormai sono già in questa discussione provo a mettere una soluzione:

(mi scuso subito con chi leggerà la soluzione; mi rendo conto che non è scorrevole, ma non sapevo come metterla giù)

Dimostriamo solo che $ a\phi(a)=b\phi(b) \Rightarrow a=b $
Sia $ a= \prod p_i^{\alpha_i} \prod r_i^{\alpha_i} $ e $ b= \prod q_i^{\beta_i} \prod r_i^{\beta_i} $, dove $ p_i,q_i, r_i $ sono primi, in modo che $ (\prod p_i^{\alpha_i},\prod q_i^{\beta_i})=1 $, $ (\prod p_i^{\alpha_i}, \prod r_i^{\alpha_i})=1 $ e $ (\prod q_i^{\beta_i}, \prod r_i^{\beta_i})=1 $
Gli $ r_i $ sono ovviamente gli stessi in a e in b.
In pratica dati i 2 numeri a e b chiamiamo $ p_i $ i primi che appartengono ad a e non a b, $ q_i $ i primi che appartengono a b e non ad a e infine $ r_i $ i primi che appartengono (alla fattorizzazione) sia di a che di b.

Ricordiamo che $ \phi(a)=\prod p_i^{\alpha_i-1}(p_i-1) \prod r_i^{\alpha_i-1} (r_i-1) $ in quanto la funzione $ \phi $ è moltiplicativa.

Scriviamo dunque l'equazione $ a\phi(a)=b\phi(b) $ come
$ \prod r_i^{2 \alpha_i-1} \prod(r_i-1) \prod p_i^{2 \alpha_i-1} \prod(p_i-1)= \prod r_i^{2 \beta_i-1} \prod(r_i-1) \prod q_i^{2 \beta_i-1} \prod(q_i-1) $

I termini $ \prod(r_i-1) $ se ne vanno poi dividiamo da entrambe le parti per $ \prod r_i^{min[2\alpha_i-1,2\beta_i-1]} $ e rimane $ \prod r_i^{2\alpha_i-2\beta_i} \prod p_i^{2 \alpha_i-1} \prod(p_i-1)= \prod r_j^{2\beta_j-2\alpha_j} \prod q_i^{2 \beta_i-1} \prod(q_i-1) $

Siccome $ (\prod p_i^{2\alpha_i-1}, \prod r_j^{2\beta_j-2\alpha_j})=1 $ e $ (\prod p_i^{2\alpha_i-1}, \prod q_i^{2 \beta_i-1})=1 $ abbiamo che $ \prod p_i^{2\alpha_i-1}| \prod(q_i-1) $.

Allo stesso modo otteniamo che $ \prod q_i^{2 \beta_i-1}|\prod(p_i-1) $
Dato che la divisibilità è anche una relazione d'ordine possiamo anche considerare i simboli di divisibilità delle ultime espressioni come $ \leq $.

Ma è evidente che $ \prod p_i^{2\alpha_i-1} > \prod(p_i-1) $ e $ \prod q_i^{2 \beta_i-1} > \prod(q_i-1) $

Le quattro relazioni creano l'assurdo poichè combinandone 3 si ottiene la relazione contraria alla quarta.
Hypotheses non fingo

String
Messaggi: 225
Iscritto il: 01 giu 2008, 17:21

Messaggio da String » 11 ott 2008, 23:38

Provo una dimostrazione più semplice.
Se $ a>b $ e $ (a,b)=1 $ allora si ha $ $ \frac {a}{b}=\frac {\phi(b)}{\phi(a)}=\frac {ka}{kb} $, che è assurdo poichè $ a>b $. Se invece $ (a,b)\neq 1 $ allora si possono semplificare i fattori comuni ottenendo $ $ \frac {a'}{b'}=\frac {\phi(b)}{\phi(a)} $. Esplicitiamo $ \phi(a) $ e $ \phi(b) $. L'equazione diventa
$ $ \frac {a'}{b'}=\frac {\displaystyle b\prod{\displaystyle \frac {p_i-1}{p_i}}}{\displaystyle a\prod{\displaystyle \frac {q_j-1}{q_j}}}=\frac {\displaystyle b'\prod{\displaystyle \frac {p_i-1}{p_i}}}{\displaystyle a'\prod{\displaystyle \frac {q_j-1}{q_j}}}\Rightarrow \displaystyle 1=\frac {\displaystyle b'^2\prod{\displaystyle \frac {p_i-1}{p_i}}}{\displaystyle a'^2\prod{\displaystyle \frac {q_j-1}{q_j}}} $.
Quindi affinchè l'equazione sia verificata, deve essere $ \displaystyle \prod \displaystyle \frac {p_i-1}{p_i}=a'^2 $ e $ \displaystyle \prod \displaystyle \frac {q_j-1}{q_j}=b'^2 $ ma ciò non può essere dato che $ (a',b')=1 $ mentre invece il MCD tra le due produttorie è $ \neq 1 $ in quanto per ipotesi di partenza $ (a,b)\neq 1 $. L'unico caso in cui l'uguaglianza è verificata è quindi quello in cui $ a=b $.
E'corretto?
"fatti non foste a viver come bruti,
ma per seguir virtute e canoscenza"(Dante)

eli9o
Messaggi: 106
Iscritto il: 14 mag 2008, 19:43

Messaggio da eli9o » 11 ott 2008, 23:58

C'è qualche passaggio che mi lascia perplesso:
in generale comunque non vale
$ \displaystyle 1= \frac{ b'^2 \prod \displaystyle \frac{p_i-1}{p_i}}{ a'^2 \prod \displaystyle \frac {q_i-1}{q_i}} \Rightarrow \prod \frac{p_i-1}{p_i}=a'^2 $ e $ \displaystyle\prod \frac{q_i-1}{q_i}=b'^2 $
Poi entrambe le produttorie danno numeri minori di 1 (ogni fattore è minore di 1), il MCD va per lo meno adattato.
Hypotheses non fingo

String
Messaggi: 225
Iscritto il: 01 giu 2008, 17:21

Messaggio da String » 12 ott 2008, 10:10

Si, mi sono accorto che quel passaggio non va bene ma comunque, dopo aver semplificato i fattori comuni a quelle produttorie, il loro rapporto deve essere un quadrato,
$ \displaystyle \frac {\displaystyle \prod{\displaystyle \frac {p_i-1}{p_i}}}{\displaystyle \prod{\displaystyle \frac {q_j-1}{q_j}}}=\displaystyle \left( \frac {a'}{b'}\right)^2 $
cosa che non può essere perchè a questo punto i primi sono tutti diversi.
Ora va bene?
"fatti non foste a viver come bruti,
ma per seguir virtute e canoscenza"(Dante)

eli9o
Messaggi: 106
Iscritto il: 14 mag 2008, 19:43

Messaggio da eli9o » 12 ott 2008, 13:02

Questa è vera (anche perchè altrimenti non sarebbe vera la tesi :lol:) ma per me non è così immediato: i $ p_i $ possono dividere i $ q_j-1 $ e allo stesso modo i $ q_i $ possono dividere i $ p_i-1 $.
Io concluderei o con una relazione d'ordine oppure forse è più bello così:
sia $ r= max[p_i, q_j] $. Quindi $ r>(p_i-1) $ e $ r>(q_i-1) \forall i \in \mathbb{N} $ . Essendo primo non ha divisori (maggiori di 1) minori di sè stesso, e dato che compare una sola volta (al numeratore o al denominatore non importa) la frazione non può essere un quadrato perfetto in quanto tale primo non ha esponente pari.
Forse sono solo precisazioni inutili e andava bene comunque.
Hypotheses non fingo

pic88
Messaggi: 741
Iscritto il: 16 apr 2006, 11:34
Località: La terra, il cui produr di rose, le dié piacevol nome in greche voci...

Messaggio da pic88 » 13 ott 2008, 10:56

eli9o ha scritto:Sia $ r= max[p_i, q_j] $. Quindi $ r>(p_i-1) $ e $ r>(q_i-1) \forall i \in \mathbb{N} $
Non ho letto i post precedenti, pero' volevo farvi osservare che, data questa definizione, si mostra facilmente che r divide sia a che b, e con lo stesso esponente, e quindi tutto si semplifica e ci si riconduce ad un caso piu' semplice (vero per ipotesi induttiva sulla somma degli esponenti).

piever
Messaggi: 645
Iscritto il: 18 feb 2006, 13:15
Località: Roma
Contatta:

Messaggio da piever » 13 ott 2008, 16:04

Bellino il problema...

Non sto riuscendo molto bene a seguire le dimostrazioni postate sopra ma mi sembra che una soluzione possa essere sintetizzata così:

1) per ogni n>1 si ha: $ \displaystyle f(n)=\frac{n}{2}\phi (n) $

2) (come nota pic): se mf(m)=nf(n) allora, detto p il primo più grande che divide il minimo comune multiplo tra m e n si ha che p divide entrambi con lo stesso esponente, quindi per la motiplicatività della funzione nf(n) mi posso ricondurre a un caso più piccolo.

Come si dimostra 1) ?

Chiamiamo g(d,n) (con d|n) la somma dei multipli di d compresi tra 1 e n.

$ \displaystyle \sum_{(i,n)=1} i =\sum_{d|n} \mu (d) g(d,n) $

Visto che $ \displaystyle g(d,n)=d\frac{\frac{n}{d}(\frac{n}{d}+1)}{2} $, sostituendo ci viene che la nostra f è uguale a:

$ \displaystyle\frac{n}{2}\sum_{d|n} \mu (d)(\frac{n}{d}+1) $

Per avere 1) ci resta da mostrare che, per ogni n>1, $ \displaystyle\sum_{d|n} \mu (d)(\frac{n}{d}+1)=\phi (n) $

Ma $ \displaystyle\sum_{d|n} \mu (d)(\frac{n}{d}+1)=\sum_{d|n} \mu (d)+\sum_{d|n} \mu (d)\frac{n}{d} $ e ora

1a) $ \displaystyle\sum_{d|n} \mu (d)=\sum_{i=0}^k (-1)^k\binom{n}{k}=(1-1)^k=0 $ (k è il numero di divisori primi di n ed è >0 in quanto n>1 per ipotesi)

1b) $ \displaystyle\sum_{d|n} \mu (d)\frac{n}{d}=\phi (n) $ in quanto $ \displaystyle\sum_{d|n} \phi(d)=n $ (double counting sulle frazioni 1/n, 2/n, 3/n,...,n/n ridotte ai minimi termini)

Fatemi sapere se qualcosa è poco chiaro.

ciau!

p.s. Ho eliminato un paio di passaggi del tutto inutili dalla dimostrazione
Ultima modifica di piever il 14 ott 2008, 16:15, modificato 1 volta in totale.
"Sei la Barbara della situazione!" (Tap)

Avatar utente
jordan
Messaggi: 3988
Iscritto il: 02 feb 2007, 21:19
Località: Pescara
Contatta:

Messaggio da jordan » 13 ott 2008, 18:28

eli9o ha scritto:I termini $ \prod(r_i-1) $ se ne vanno poi dividiamo da entrambe le parti per $ \prod r_i^{min[2\alpha_i-1,2\beta_i-1]} $ e rimane $ \prod r_i^{2\alpha_i-2\beta_i} \prod p_i^{2 \alpha_i-1} \prod(p_i-1)= \prod r_j^{2\beta_j-2\alpha_j} \prod q_i^{2 \beta_i-1} \prod(q_i-1) $
Sicuro? :roll:
piever ha scritto:Bellino il problema...


Grazie, appena ho un po di tempo leggo con calma la tua soluzione :wink:
The only goal of science is the honor of the human spirit.

eli9o
Messaggi: 106
Iscritto il: 14 mag 2008, 19:43

Messaggio da eli9o » 13 ott 2008, 19:36

In effetti la precisione è un po' andata a farsi friggere. Provo a dirlo meglio (sperando che sia giusto)

Abbiamo la relazione
$ \displaystyle \prod r_i^{2\alpha_i-1} \prod (r_i-1) \prod p_i^{2\alpha_i-1} \prod (p_i-1) = \displaystyle \prod r_i^{2\beta_i-1} \prod (r_i-1) \prod q_i^{2\beta_i-1} \prod (q_i-1) $

A parte che non ho capito perchè mi manda a capo l'uno, questa non dava problemi giusto?

Poi cambiamo lettere così forse c'è meno casino.
Siano gli $ s_i $ quegli $ r_i $ che hanno esponente maggiore nell' LHS (cioè quelli che hanno il rispettivo $ \alpha_i $ maggiore del rispettivo $ \beta_i $)
Siano gli $ t_i $ quegli $ r_i $ che hanno esponente maggiore nell' RHS (cioè quelli che hanno il rispettivo $ \beta_i $ maggiore del rispettivo $ \alpha_i $)

Quindi dividiamo per $ \displaystyle \prod s_i^{2\beta_i-1} \prod t_i^{2 \alpha_i-1} $
Non penso che il problema fosse nemmeno il mandar via gli $ r_i-1 $. Poi vanno via anche gli $ r_i $ che non sono né $ s_i $ né $ t_i $ perché hanno l'esponente uguale. A questo punto dovrebbe rimanere

$ \displaystyle \prod s_i^{2\alpha_i-2\beta_i} \prod p_i^{2\alpha_i-1} \prod (p_i-1) = \prod t_i^{2\beta_i-2\alpha_i} \prod q_i^{2\beta_i-1} \prod (q_i-1) $

Ora questa sarebbe la relazione citata da jordan scritta (spero) un po' meglio.
Per il resto della dimostrazione dovrebbe bastare cambiare un $ r_j $ con un $ t_i $.
Hypotheses non fingo

Avatar utente
jordan
Messaggi: 3988
Iscritto il: 02 feb 2007, 21:19
Località: Pescara
Contatta:

Messaggio da jordan » 13 ott 2008, 21:27

eli9o ha scritto:In effetti la precisione è un po' andata a farsi friggere. Provo a dirlo meglio (sperando che sia giusto)

Abbiamo la relazione
$ \displaystyle \prod r_i^{2\alpha_i-1} \prod (r_i-1) \prod p_i^{2\alpha_i-1} \prod (p_i-1) = \displaystyle \prod r_i^{2\beta_i-1} \prod (r_i-1) \prod q_i^{2\beta_i-1} \prod (q_i-1) $

A parte che non ho capito perchè mi manda a capo l'uno, questa non dava problemi giusto?

Poi cambiamo lettere così forse c'è meno casino.
Siano gli $ s_i $ quegli $ r_i $ che hanno esponente maggiore nell' LHS (cioè quelli che hanno il rispettivo $ \alpha_i $ maggiore del rispettivo $ \beta_i $)
Siano gli $ t_i $ quegli $ r_i $ che hanno esponente maggiore nell' RHS (cioè quelli che hanno il rispettivo $ \beta_i $ maggiore del rispettivo $ \alpha_i $)

Quindi dividiamo per $ \displaystyle \prod s_i^{2\beta_i-1} \prod t_i^{2 \alpha_i-1} $
Non penso che il problema fosse nemmeno il mandar via gli $ r_i-1 $. Poi vanno via anche gli $ r_i $ che non sono né $ s_i $ né $ t_i $ perché hanno l'esponente uguale. A questo punto dovrebbe rimanere

$ \displaystyle \prod s_i^{2\alpha_i-2\beta_i} \prod p_i^{2\alpha_i-1} \prod (p_i-1) = \prod t_i^{2\beta_i-2\alpha_i} \prod q_i^{2\beta_i-1} \prod (q_i-1) $

Ora questa sarebbe la relazione citata da jordan scritta (spero) un po' meglio.
Per il resto della dimostrazione dovrebbe bastare cambiare un $ r_j $ con un $ t_i $.
very good :wink:
io concluderei $ \prod{p_i-1}<\prod{p^{2\alpha_i-1}} \le \prod{q_i-1} < \prod{q_i^{2\beta_i-1}} \le \prod{p_i-1} $
The only goal of science is the honor of the human spirit.

Rispondi