Calcolo $\phi(100)$ dove $\phi$ è la funzione totient
La domanda:
Calcolare $\phi(100)$
Il mio tentativo:
Ho tentato di calcolare la funzione totiente al valore 100, ovvero:
$$\phi(100)$$
Per fare ciò, ho utilizzato la regola del prodotto della funzione totient:
$\phi(ab)$ = $\phi(a)$ $\times$ $\phi(b)$
Così $\phi(100)$ = $\phi(25)$ $\times$ $\phi(4)$
= $\phi(5)$ $\times$ $\phi(5)$ $\times$ $\phi(2)$ $\times$ $\phi(2)$
= 4 $\times$ 4 $\times$ 1 $\times$ 1
= 16.
La confusione (se vuoi)
Tuttavia, quando ho cercato la funzione totale di 100 in linea, ne è risultata costantemente 40. Questa mi sembra una risposta più appropriata, ma non sono del tutto sicuro di dove ho sbagliato nel mio tentativo. Potresti dirmi dove ho sbagliato?
Grazie!
Risposte
Bene, @Arthur mi ha chiarito questo nei commenti, quindi risponderò alla mia domanda:
$\phi(ab)$ = $\phi(a)$ $\times$ $\phi(b)$, solo se aeb sono co-prime .
Allora mentre $\phi(100)$ = $\phi(25)$ $\times$ $\phi(4)$ perché 25 e 4 sono co-primes, $\phi(100)$ = $\phi(5)$ $\times$ $\phi(5)$ $\times$ $\phi(2)$ $\times$ $\phi(2)$non è vero perché i 2 non sono coprimi e nemmeno i 5 sono co-primi.
Così, $\phi(100)$ = $\phi(25)$ $\times$ $\phi(4)$.
$\phi(25)$ = 20 (Possiamo valutarlo tramite la formula $\phi(p^n) = p^{n-1}(p-1)$, quindi $ \ phi (5 ^ 2) = 5 ^ {1} (4) = 5 \ times 4 = 20.
$ \ phi (4) $ = 2.
$ \ implica$$\phi(100)$ = $20 \times 2$ = 40.
Grazie a @Arthur e @DreiCleaner per aver chiarito questo aspetto e @JWTanner per aver suggerito alcuni modi per migliorare questa risposta!
Come sottolineato nei commenti, $5$ e $5$non sono coprimi, quindi non puoi usare la regola del prodotto lì. Lo stesso per$2$ e $2$. Suggerisco semplicemente di contare direttamente, poiché sono coinvolti numeri piuttosto piccoli.
Esiste, tuttavia, anche una semplice regola per $\phi(a^n)$ puoi usare, in quella fase, per $\phi(4)$ e $\phi(25)$, o immediatamente per $100=10^2$. Se non hai visto quella regola, ecco un piccolo suggerimento per iniziare:
Quanti numeri da 0 a 10 sono coprimi con 10? Che ne dici di da 10 a 20? E da 20 a 30? Che ne dici di [e così via ...]
Infine, c'è una differenza tra essere coprimi con 10 e coprimi con 100?
Va bene ... regola 1:
Se $p$ è il primo $\phi(p) = p-1$. Dovrebbe essere chiaro come$1$ per $p-1$ sono tutti relativamente primi per $p$.
Regola 2:
Se $n = p^k$ poi $\phi(p) = p^{k-1}(p-1)$.
Non così ovvio all'inizio, ma se si considerano tutti i numeri tra $1$ e $p^k-1$ sono della forma $q*p + r; 0\le r < p$ di $p*p + r$ relativamente primo se un solo se $r\ne 0$ e così poi i numeri $q*p + 1, q*p+2, ....q*p+(n-1)$ sono relativamente prime mentre $q*p + 0$non è. Per ogni$q$ ci sono $p-1$ di questi $q*p + r; r\ne 0$ e la domanda rimane quanti $q$ci sono? Bene,$q$ può essere piccolo quanto $0$ per $n=1,...., p-1$ e grande quanto $p^{k-2}$ per $p^{k-1} +1=p*p^{k-1}+1,.., $ per $p^k-1 = p*p{k-1} + (p-1)$. quindi ci sono$p^{k-1}$ possibile $q$se così ci sono $(p-1)\times p^{k-1}$ o $p^{k-1}(p-1)$ numeri relativamente primi a $p^k$.
La regola finale è
regola 3: If $\gcd(a,b)=1$ poi $\phi(ab) = \phi(a)\phi(b)$. Questo con le altre regole può determinare$\phi(n)$ per tutti i numeri interi positivi $n$ considerando la scomposizione in fattori primi di $n$. Se$n = \prod p_i^{k_i}$ poi $\phi (n) = \prod \phi(p_i^{k_i}) = \prod( (p-1)p_i^{k_i-1})$.
Così $\phi (100) = \phi (4)\phi (25)=\phi(2^2) \phi(5^2) = (2-1)2^{2-1}(5-1)25^{2-1} = 2*20 = 40$.
Ora il motivo della regola 3: due le prime simili alle regole ma un po 'più di grattacapi da derivare. Ma si può fare.
Ecco un argomento approssimativo :
Fuori da ogni $a$ numeri $\phi(a)$ di loro saranno relativamente primi a $a$ e $(a-\phi(a))$ di loro non lo faranno.
Quindi fuori $ab$ numeri $b\phi(a)$ di sarà relativamente primo a $a$ e $(ab - b\phi(a)$ non sarà.
Fuori da ogni $b$ numeri $\phi(b)$ di loro saranno relativamente primi a $b$ e $(b-\phi(b))$ di loro non lo faranno.
Quindi fuori $ab$ numeri $a\phi(b)$ di sarà relativamente primo a $a$ e $(ab - a\phi(b))$ non sarà.
E fuori $ab$ numeri $(b-\phi(b))(a-\phi(a))$non sarà relativamente primo per nessuno dei due $a$ né $b$.
Utilizzo dell'inclusione / esclusione
$\phi(ab) =$ il numero di numeri relativamente primi a $ab$ meno di $ab=$
il numero di numeri relativamente primi per entrambi $a$ e a $b=$
Il numero totale di numeri fino a $ab$ meno i numeri che non sono primi relativamente $a$ meno il numero a cui non è relativamente primo $b$ più (per evitare il doppio conteggio) i numeri che non sono primi tra loro $=$
$ab - (a-\phi(a))b - (b-\phi(b))a + (a-\phi(a))(b-\phi(b) =$
$ab - ab +b\phi(a) -ab +a\phi(b) +ab - b\phi(a) -a\phi(b) + \phi(a)\phi(b) =$
$\phi(a)\phi(b)$
Ta-da.