Teorema cardinalità sui numeri primi
Il teorema non si chiama così ma sulle note si chiama semplicemente teorema 2.10.
Ecco cosa dice il teorema:
Siano p, q due numeri primi, si ha allora:
1. $ \phi(p) = p - 1 $
2. $ \phi(pq) = (p - 1)(q - 1) $
3. $ \phi(p^k) = p^k - p^(k-1) $
4. $ \phi(p^k q^h) = (p^k - p^(k-1))(q^h - q^(h-1)) $
1. Allora il primo caso è abbastanza semplice, basta considerare i p numeri da 0 a $ p-1 $ e questi, tranne lo 0, sono primi con p.
2. Come nel caso 1 consideriamo i $pq$ numeri da $0$ a $pq-1$. Ci sono $q$ multipli di $p$: $0,p,2p, \ldots, (q-1)p $ e $p$ multipli di $q$: $0,q,2q, \ldots, (p-1)q$. Quello che non capisco è perché nelle note scrive che questi sono gli unici a non essere primi con $pq$ inoltre non capisco questa uguaglianza:
$ \phi(pq) = pq - p -q + 1 $
Da cui si ottiene la tesi.
Anche il punto 3 e 4 mi creano problemi ma intanto vorrei capire prima questo punto perché per il punto 4 il ragionamento è analogo.
Ecco cosa dice il teorema:
Siano p, q due numeri primi, si ha allora:
1. $ \phi(p) = p - 1 $
2. $ \phi(pq) = (p - 1)(q - 1) $
3. $ \phi(p^k) = p^k - p^(k-1) $
4. $ \phi(p^k q^h) = (p^k - p^(k-1))(q^h - q^(h-1)) $
1. Allora il primo caso è abbastanza semplice, basta considerare i p numeri da 0 a $ p-1 $ e questi, tranne lo 0, sono primi con p.
2. Come nel caso 1 consideriamo i $pq$ numeri da $0$ a $pq-1$. Ci sono $q$ multipli di $p$: $0,p,2p, \ldots, (q-1)p $ e $p$ multipli di $q$: $0,q,2q, \ldots, (p-1)q$. Quello che non capisco è perché nelle note scrive che questi sono gli unici a non essere primi con $pq$ inoltre non capisco questa uguaglianza:
$ \phi(pq) = pq - p -q + 1 $
Da cui si ottiene la tesi.
Anche il punto 3 e 4 mi creano problemi ma intanto vorrei capire prima questo punto perché per il punto 4 il ragionamento è analogo.
Risposte
Ciao, Shruikan. Per piacere aggiungi un po' di parentesi, quello che hai scritto ha poco senso.
Per esempio credo che il punto 3 non sia $ \phi(p^k) = p^k - p^k-1 = -1 $, ma $ \phi(p^k) = p^k - p^(k-1) $.
Sei sicuro di essere uno studente delle superiori? In quale classe si fanno questi argomenti?
Per esempio credo che il punto 3 non sia $ \phi(p^k) = p^k - p^k-1 = -1 $, ma $ \phi(p^k) = p^k - p^(k-1) $.
Sei sicuro di essere uno studente delle superiori? In quale classe si fanno questi argomenti?
Che funzione è $phi$ ?
"Indrjo Dedej":
Che funzione è $phi$ ?
La funzione $phi$ di eulero, definita così: $phi: \mathbb{N^{>0}} \to \mathbb{N^{>0}}$ tale che $\forall n \in \mathbb{N^{>0}}$ $phi(n) = |{m \in \mathbb{N^{>0}}| MCD(n, m) = 1 and m < n}|$, cioè $phi(n)$ è il numero di interi positivi comprimi con $n$ e minori di $n$.
Es: $phi(2) = 1$, $phi(4) = 2$, $phi(3) = 2$, $phi(6) = 2$
Ho modificato il post e le formule sbagliate.
Il testo su cui sto studiando si chiama "La matematica della scuola media" di Renzo Sprugnoli. E' un testo universitario che prepara al test di ammissione e quindi affronta argomenti delle scuole medie ma ad un livello universitario. In questo caso i numeri primi.
Nella fretta mi sono scordato di scrivere la funzione $phi$.
Come già detto, $\phi$ è la funzione toziente di Eulero definita, per ogni intero positivo $ n $, come il numero degli interi compresi tra 1 ed $ n $ che sono coprimi con $n$, cioè se non hanno divisori in comune, eccetto $1$.
Il testo su cui sto studiando si chiama "La matematica della scuola media" di Renzo Sprugnoli. E' un testo universitario che prepara al test di ammissione e quindi affronta argomenti delle scuole medie ma ad un livello universitario. In questo caso i numeri primi.
Nella fretta mi sono scordato di scrivere la funzione $phi$.
Come già detto, $\phi$ è la funzione toziente di Eulero definita, per ogni intero positivo $ n $, come il numero degli interi compresi tra 1 ed $ n $ che sono coprimi con $n$, cioè se non hanno divisori in comune, eccetto $1$.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo