Alice, Bob e Eva — La funzione toziente

“Abbiamo detto che si chiama funzione toziente, e si indica con φ(n), il numero di interi positivi minori o uguali a n e primi rispetto a n”.

“Sì, c'è una formula per calcolarla?”.

“Eh, magari. No, fino ad oggi non è stata trovata nessuna formula diretta”.

“E quindi come si fa? Per tentativi?”.

“Si può procedere per tentativi, sì, soprattutto se n è piccolo. Però conosciamo un po' di proprietà che possono aiutarci. Per esempio, se p è primo allora φ(p) = p-1”.

“Va bene, questa è facile, se p è primo tutti gli interi minori di p sono primi rispetto a p”.

“Quindi, tanto per fare un esempio, φ(5) = 4. Cosa puoi dirmi di φ(25)?”.

“Non è un numero primo, non so, dovrei fare i conti”.

“Però è una potenza di un numero primo, puoi ragionare un po' su questo fatto”.

“Vediamo: 25 contiene solo il fattore 5, quindi ogni numero primo rispetto ad esso non dovrà contenere il fattore 5”.

“Quanti sono i numeri minori o uguali di 25 che contengono il fattore 5?”.

“Tutti i multipli di 5”.

“E quanti sono?”.

“Bè, 5. Sono 5, 10, 15, 20, 25”.

“Tutti gli altri numeri sono primi con 25, quindi”.

“Sì, giusto. Quindi ci sono 25 numeri minori o uguali a 25, 5 dei quali non sono primi rispetto a 5. Quindi ne rimangono 20: φ(25) = 20”.

“E se ti chiedo di calcolare φ(5³)?”.

“Dovrei ragionare come prima, tra tutti i 125 numeri che posso prendere in considerazione ce n'è uno ogni 5 che è multiplo di 5”.

“E che devi togliere”.

“Sì, esatto, quindi φ(5³) = 5³-5²”.

“In generale, se p è primo allora φ(p^k) = p^k-p^k-1. Questa è una prima regolina”.

“Ce ne sono altre?”.

“Sì, ce n'è una che è molto comoda per i calcoli. Dice questo: se n e m sono due interi primi tra loro, allora φ(nm) = φ(n)φ(m). Però è un po' brigosa da dimostrare, se permetti ti faccio vedere solo qualche esempio”.

“Ok, va bene”.

“Per esempio, vuoi calcolare φ(360). Non è un numero primo, quindi puoi scomporlo, e risulta che 360 = 2³3²5”.

“Ok, sono tre fattori primi tra loro, quindi posso scrivere φ(360) = φ(2³)φ(3²)φ(5)”.

“Ora, per quanto riguarda φ(2³), puoi applicare la seconda formula che abbiamo scritto”.

“Giusto: φ(2³) = 2³-2² = 4”.

“Per φ(3²) puoi procedere allo stesso modo”.

“Sì, è vero: φ(3²) = 3²-3 = 6”.

“E infine φ(5)”.

“Che è uguale a 4”.

“Quindi φ(360) = 4·6·4 = 96”.

“Bene, se sappiamo scomporre in fattori sappiamo anche calcolare φ, a questo punto”.

“Esatto. Il problema è proprio lì”.

⇐ · ⇒