Quasi come la phi, ma i pari non li vogliamo!

Numeri interi, razionali, divisibilità, equazioni diofantee, ...
Rispondi
Avatar utente
salva90
Messaggi: 1314
Iscritto il: 19 ott 2006, 18:54
Località: Carrara

Quasi come la phi, ma i pari non li vogliamo!

Messaggio da salva90 » 23 giu 2008, 23:03

Questa mattina, risolvendo un problema, mi sono trovato di fronte alla seguente questione.

Dato un intero n dispari, definiamo $ \gamma(n) $ come la funzione che associa ad n il numero di interi dispari minori di esso e con esso coprimi.
Allora $ \gamma(n)=\frac12\cdot\varphi(n) $, dove $ \varphi(n) $ è la classica funzione di Eulero.

Invito gli utenti poco esperti a trovare una dimostrazione (è facile facile, garantisco).

Chiedo inoltre se in gara potrei dare per scontato tale fatto, o se devo dimostrarlo ogni volta.


Good work :wink:
[url=http://www.myspace.com/italiadimetallo][img]http://img388.imageshack.us/img388/4813/italiadimetallogn7.jpg[/img][/url]

Stex19
Messaggi: 139
Iscritto il: 26 mar 2008, 15:12
Località: Genova

Re: Quasi come la phi, ma i pari non li vogliamo!

Messaggio da Stex19 » 24 giu 2008, 00:28

salva90 ha scritto:Questa mattina, risolvendo un problema, mi sono trovato di fronte alla seguente questione.

Dato un intero n dispari, definiamo $ \gamma(n) $ come la funzione che associa ad n il numero di interi dispari minori di esso e con esso coprimi.
Allora $ \gamma(n)=\frac12\cdot\varphi(n) $, dove $ \varphi(n) $ è la classica funzione di Eulero.

Invito gli utenti poco esperti a trovare una dimostrazione (è facile facile, garantisco).

Chiedo inoltre se in gara potrei dare per scontato tale fatto, o se devo dimostrarlo ogni volta.


Good work :wink:

provo:
in sostanza bisogna dimostrare che i coprimi minori di n pari sono quanti i dispari.
se n è primo, è banale, perchè i coprimi sono tutti i numeri che lo precedono, quindi i pari sono quanti i disapri.
se n non è primo, ma fattorizzabile in $ \displaystyle n=x_1^{i_1}x_2^{i_2}.....x_m^{i_m} $ (con $ \displaystylex_k $ diverso da 2), i coprimi di n sono tutti i numeri precedenti esclusi i multipli di $ \displaystile x_k $ con k da 1 a m.
ma i multipli di $ x_k $ minori di n sono $ jx_k $ con j da 1 a $ \displaystyle\frac{n}{x_k}-1 $.
sono quindi un numero pari, e i dispari sono quanti i pari.
lo stesso vale per gli altri fattori di n.

nicelbole
Messaggi: 14
Iscritto il: 16 mag 2007, 16:47

Messaggio da nicelbole » 24 giu 2008, 09:50

Se d è un dispari minore di n e primo con n, p=n-d è un pari minore di n e primo con n; allo stesso modo se p è un pari minore di n e primo con n, d=n-p è un dispari minore di n e primo con n.
Dunque tra l'insieme dei d e dei p c'è una corrispondenza biunivoca, ed essi sono in numero uguale.

Avatar utente
salva90
Messaggi: 1314
Iscritto il: 19 ott 2006, 18:54
Località: Carrara

Messaggio da salva90 » 24 giu 2008, 10:45

nicelbole ha scritto:Se d è un dispari minore di n e primo con n, p=n-d è un pari minore di n e primo con n; allo stesso modo se p è un pari minore di n e primo con n, d=n-p è un dispari minore di n e primo con n.
Dunque tra l'insieme dei d e dei p c'è una corrispondenza biunivoca, ed essi sono in numero uguale.
perfetto, era questa che volevo saltasse fuori :wink:
[url=http://www.myspace.com/italiadimetallo][img]http://img388.imageshack.us/img388/4813/italiadimetallogn7.jpg[/img][/url]

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

Messaggio da piever » 24 giu 2008, 16:38

Ma scusate, questo è uno dei primi lemmi che si fa quando si studiano le proprietà di phi odd. Potrete trovare di più su "Zwing Czauklasi", libro di un giovane semisconosciuto ballerino sloveno sul problem solving... Parla di phi odd nel capitolo: "Wedno Doryczy Przediegu" (che vuol dire: "Ah già è vero, anche stavolta ho perso punti sul problema più facile")...

@ salva: credo di avere in mente il problema che stavi risolvendo :wink:
"Sei la Barbara della situazione!" (Tap)

AndBand89
Messaggi: 179
Iscritto il: 10 mar 2008, 18:17
Località: San Giovanni al Natisone(diciamo Udine dai)

Messaggio da AndBand89 » 25 giu 2008, 17:01

piever ha scritto:"Wedno Doryczy Przediegu"
Vergogna, c'è un errore di grammatica!Si scrive "Wyedno"! Eh, è amico mio sto ballerino... :lol: anche di Fede90, ma questa è un'altra storia...vero Fede? :lol: (sperando che Fede legga)

Rispondi