[EX] - Sui coprimi
Esercizio (semplice). Dire quanti sono i naturali \(\displaystyle n < 4641 \) t.c. \(\displaystyle (4641,n)=1 \).
Con \(\displaystyle (\cdot, \cdot) \) indico il massimo comun divisore.
Edit. Dovevo essere ubriaco. Comunque pensavo all'MCD quando ho scritto mcm. Mi scuso per l'increscioso errore.
Con \(\displaystyle (\cdot, \cdot) \) indico il massimo comun divisore.
Edit. Dovevo essere ubriaco. Comunque pensavo all'MCD quando ho scritto mcm. Mi scuso per l'increscioso errore.
Risposte
Spoilerizzo una soluzione (non la migliore 
).
).
Penso che si volesse intendere MCD, come del resto s'intuisce dalla condizione \(\displaystyle (4641,n)=1 \) ed anche dal titolo dove si parla di " coprìmi " ( attenzione all'accento che sta sulla "i" e non sulla "o" 
).
Se è così allora effettivamente la funzione \(\displaystyle \phi \) di Eulero risolve immediatamente il problema :
\(\displaystyle \phi(4641)=\phi(3\cdot 7\cdot 13\cdot 17)=\phi(3)\cdot \phi(7)\cdot\phi(13)\cdot\phi(17)=2\cdot 6\cdot 12\cdot 16=2304 \)
Volendo ( e dovendo) evitare in questa sezione l'uso di \(\displaystyle \phi \), si può ragionare elementarmente come segue.
Intanto è : \(\displaystyle 4641= 3\cdot 7\cdot 13\cdot 17\)
Consideriamo allora la successione:
(a) \(\displaystyle 1,2,3,....,4640,4641 \)
Per risolvere la questione cominciamo col togliere dalla (a) i multipli di 3 che sono \(\displaystyle \frac{4641}{3} = 1547\) ( qualcuno, se crede, lo provi ) e dunque i termini della (a) da 4641 scendono a
\(\displaystyle 4641-1547=3094\)
Da questi occorre sottrarre i multipli di 7. Ragionando in maniera analoga , i termini scendono a :
\(\displaystyle 3094-\frac{3094}{7}=2652 \)
Ora occorre eliminare i multipli di 13 ed il risultato scende ancora :
\(\displaystyle 2652-\frac{2652}{13}=2448 \)
Eliminando infine i multipli di 17 risulta:
\(\displaystyle 2448-\frac{2448}{17}=2304 \)
C.V.D.
).Se è così allora effettivamente la funzione \(\displaystyle \phi \) di Eulero risolve immediatamente il problema :
\(\displaystyle \phi(4641)=\phi(3\cdot 7\cdot 13\cdot 17)=\phi(3)\cdot \phi(7)\cdot\phi(13)\cdot\phi(17)=2\cdot 6\cdot 12\cdot 16=2304 \)
Volendo ( e dovendo) evitare in questa sezione l'uso di \(\displaystyle \phi \), si può ragionare elementarmente come segue.
Intanto è : \(\displaystyle 4641= 3\cdot 7\cdot 13\cdot 17\)
Consideriamo allora la successione:
(a) \(\displaystyle 1,2,3,....,4640,4641 \)
Per risolvere la questione cominciamo col togliere dalla (a) i multipli di 3 che sono \(\displaystyle \frac{4641}{3} = 1547\) ( qualcuno, se crede, lo provi
) e dunque i termini della (a) da 4641 scendono a \(\displaystyle 4641-1547=3094\)
Da questi occorre sottrarre i multipli di 7. Ragionando in maniera analoga , i termini scendono a :
\(\displaystyle 3094-\frac{3094}{7}=2652 \)
Ora occorre eliminare i multipli di 13 ed il risultato scende ancora :
\(\displaystyle 2652-\frac{2652}{13}=2448 \)
Eliminando infine i multipli di 17 risulta:
\(\displaystyle 2448-\frac{2448}{17}=2304 \)
C.V.D.
Sì, in effetti io pensavo alla funzione di Eulero, ma ammetto che non si tratta di una conoscenza proprio elementare - e poi, tra l'altro, esiste un'espressione analitica di tale funzione? -.
- Fesseria -
Si veda sotto il ragionamento corretto, fatto da ciromario.
- Fesseria -
Si veda sotto il ragionamento corretto, fatto da ciromario.
Sia \(\displaystyle n=p_1^{k_1}\cdot p_2^{k_2}...\cdot p_r^{k_r} (p_i=\text{numero-primo}) \)
la scomposizione di n in fattori primi. La funzione \(\displaystyle \phi \) di Eulero ( detta anche "indicatrice di Gauss") è:
(1) \(\displaystyle \phi(n)=n( 1-\frac{1}{p_1} ) (1-\frac{1}{p_1})(1-\frac{1}{p_2})...(1-\frac{1}{p_r}) \)
La funzione di Eulero è moltiplicativa nel senso che ,se a e b sono coprimi, risulta :
\(\displaystyle \phi(ab)=\phi(a)\phi(b) \)
Se \(\displaystyle n=p^k \), dalla (1) si ricava in particolare che è :
\(\displaystyle \phi(p^k)=p^{k-1}(p-1) \)
che non mi pare corrisponda alla formula da te indicata nel rilancio.
la scomposizione di n in fattori primi. La funzione \(\displaystyle \phi \) di Eulero ( detta anche "indicatrice di Gauss") è:
(1) \(\displaystyle \phi(n)=n( 1-\frac{1}{p_1} ) (1-\frac{1}{p_1})(1-\frac{1}{p_2})...(1-\frac{1}{p_r}) \)
La funzione di Eulero è moltiplicativa nel senso che ,se a e b sono coprimi, risulta :
\(\displaystyle \phi(ab)=\phi(a)\phi(b) \)
Se \(\displaystyle n=p^k \), dalla (1) si ricava in particolare che è :
\(\displaystyle \phi(p^k)=p^{k-1}(p-1) \)
che non mi pare corrisponda alla formula da te indicata nel rilancio.
Neanche a me pare che corrisponda. Infatti sono un nabbo.
"ciromario":
Volendo ( e dovendo) evitare in questa sezione l'uso di \(\displaystyle \phi \), si può ragionare elementarmente come segue. [... ometto la dimostrazione ...]
C.V.D.
Veramente notevole, davvero!
Anzi esemplare mostra di ragionamento matematico.
Nella mia, come detto, senza passare per la $\phi$ andavo a togliere i multipli dei fattori primi facendo una marea di MCD uno alla volta.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo