Esercizi sulla funzione di eulero
iniziamo con questo:
Trovare tutti gli $n$ per cui $F(n)=12$
Per $F(n)$ chiaramente si intende la funzione di eulero. Una soluzione è sicuramente 13 perchè essendo numero primo tutti i numeri che si trovano prima di lui non avranno alcun divisore comune con 13, ma per trovare le altre soluzioni non ho capito come bisogna procedere, nonostante il professore lo abbia spiegato.
Un anima paziente che mi spiega come si risolve l'esercizio?
Trovare tutti gli $n$ per cui $F(n)=12$
Per $F(n)$ chiaramente si intende la funzione di eulero. Una soluzione è sicuramente 13 perchè essendo numero primo tutti i numeri che si trovano prima di lui non avranno alcun divisore comune con 13, ma per trovare le altre soluzioni non ho capito come bisogna procedere, nonostante il professore lo abbia spiegato.
Un anima paziente che mi spiega come si risolve l'esercizio?
Risposte
Un metodo generale, stando a quanto ricordo, non esiste. Devi ragionare per casi, ricordando le proprietà della funzione $\phi$ di Eulero:
1) $\phi(p)=p-1$, con $p$ primo;
2) $\phi(r*s)=\phi(r)*\phi(s)$, con $r$ e $s$ primi;
3) $\phi(p^n)=p^n-p^(n-1)$, con $p$ primo.
1) $\phi(p)=p-1$, con $p$ primo;
2) $\phi(r*s)=\phi(r)*\phi(s)$, con $r$ e $s$ primi;
3) $\phi(p^n)=p^n-p^(n-1)$, con $p$ primo.
io lo farei così ma non so se è un metodo ottimale 
sia $n=p_1^(s_1)*p_2^(s_2)*...*p_n^(s_n)$ la fattorizzazione di n
allora $F(n)=F(p_1^(s_1))*F(p_2^(s_2))*...*F(p_n^(s_n))$ ora sappiamo che se p è un primo $F(p^h)=p^h-p^(h-1)$
quindi $(p_1^(s_1)-p_1^(s_1-1))*(p_2^(s_2)-p_2^(s_2-1))*...*(p_n^(s_n)-p_n^(s_n-1))=12$
12 lo possiamo scomporre come 4*3,2*2*3,6*3,12*1
considero la prima scomposizione: devo trovare due primi p,q e due interi h,k tali che:$p^h-p^(h-1)=4$ e $q^k-q^(k-1)=3$
$p^(h-1)(p-1)=4$ ora ho tre casi:
$p^(h-1)=4,p-1=1->p=2,h=3$
$p^(h-1)=2,p-1=2$ nessuna soluzione
$p^(h-1)=1,p-1=4->p=5,h=1$
$q^(k-1)(q-1)=3$ ho due casi:
$q^(k-1)=3,q-1=1$ nessuna soluzione
$q^(k-1)=1,q-1=3$ nessuna soluzione (q=4 non è un primo)
quindi la prima scomposizione non dà risultati. bisognerebbe provare le altre...
sia $n=p_1^(s_1)*p_2^(s_2)*...*p_n^(s_n)$ la fattorizzazione di n
allora $F(n)=F(p_1^(s_1))*F(p_2^(s_2))*...*F(p_n^(s_n))$ ora sappiamo che se p è un primo $F(p^h)=p^h-p^(h-1)$
quindi $(p_1^(s_1)-p_1^(s_1-1))*(p_2^(s_2)-p_2^(s_2-1))*...*(p_n^(s_n)-p_n^(s_n-1))=12$
12 lo possiamo scomporre come 4*3,2*2*3,6*3,12*1
considero la prima scomposizione: devo trovare due primi p,q e due interi h,k tali che:$p^h-p^(h-1)=4$ e $q^k-q^(k-1)=3$
$p^(h-1)(p-1)=4$ ora ho tre casi:
$p^(h-1)=4,p-1=1->p=2,h=3$
$p^(h-1)=2,p-1=2$ nessuna soluzione
$p^(h-1)=1,p-1=4->p=5,h=1$
$q^(k-1)(q-1)=3$ ho due casi:
$q^(k-1)=3,q-1=1$ nessuna soluzione
$q^(k-1)=1,q-1=3$ nessuna soluzione (q=4 non è un primo)
quindi la prima scomposizione non dà risultati. bisognerebbe provare le altre...
Rubik ti ringrazio, ho capito il tuo ragionamento e sono riuscito a risolvere.
Ora un altro tipo di esercizio che proprio non riesco a capire=
Determinare il valore di n tale che il (massimo comune divisore) $(n,F(n))=1$
F(n) chiaramente è la funzione di Eulero.
Ora un altro tipo di esercizio che proprio non riesco a capire=
Determinare il valore di n tale che il (massimo comune divisore) $(n,F(n))=1$
F(n) chiaramente è la funzione di Eulero.
partiamo da un caso particolare $n=p^k$ con $k>=1$ e $p$ primo
$(F(n),n)=(p^k-p^(k-1),p^k)=(p^(k-1)(p-1),p^k)=p^(k-1)$
affinchè sia $(F(n),n)=1$ deve essere $k=1$.
questo suggerisce che, essendo $F(nm)=F(n)*F(m)$, i primi nella scomposizione di n devo compararire tutti con esponente al più 1
ora sarà quindi $F(n)=(p_1-1)(p_2-1)*...*(p_n-1)$ e $n=p_1*p_2*...p_n$, $n$ e $F(n)$ hanno fattori in comune?
solamente se $p_i=p_j+1$ per qualche i,j. gli unici due primi che differiscono di 1 sono 2 e 3, che quindi non devono comparire contemporaneamente nella scomposizione di n.
concludendo $(F(n),n)=1$ per ogni n che si scrive come un prodotto di primi in cui non compaiono contemporaneamente 2 e 3. spero di essere stato chiaro
$(F(n),n)=(p^k-p^(k-1),p^k)=(p^(k-1)(p-1),p^k)=p^(k-1)$
affinchè sia $(F(n),n)=1$ deve essere $k=1$.
questo suggerisce che, essendo $F(nm)=F(n)*F(m)$, i primi nella scomposizione di n devo compararire tutti con esponente al più 1
ora sarà quindi $F(n)=(p_1-1)(p_2-1)*...*(p_n-1)$ e $n=p_1*p_2*...p_n$, $n$ e $F(n)$ hanno fattori in comune?
solamente se $p_i=p_j+1$ per qualche i,j. gli unici due primi che differiscono di 1 sono 2 e 3, che quindi non devono comparire contemporaneamente nella scomposizione di n.
concludendo $(F(n),n)=1$ per ogni n che si scrive come un prodotto di primi in cui non compaiono contemporaneamente 2 e 3. spero di essere stato chiaro
chiarissimo, grazie mille.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo