Calculando $\phi(100)$ Onde $\phi$ é a função totient
A questão:
Calcular $\phi(100)$
Minha tentativa:
Tentei calcular a função totient no valor 100, ou seja:
$$\phi(100)$$
Para fazer isso, usei a regra de produto da função totient:
$\phi(ab)$ = $\phi(a)$ $\times$ $\phi(b)$
assim $\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.
A confusão (se você quiser)
No entanto, quando pesquisei a função totient de 100 online, encontrei consistentemente 40. Esta me parece uma resposta mais apropriada, mas não tenho certeza de onde errei na minha tentativa. Você poderia me dizer onde errei?
Obrigado!
Respostas
Bem, @Arthur esclareceu isso para mim nos comentários, então vou responder minha própria pergunta:
$\phi(ab)$ = $\phi(a)$ $\times$ $\phi(b)$, somente se aeb forem primos .
Por enquanto $\phi(100)$ = $\phi(25)$ $\times$ $\phi(4)$ porque 25 e 4 são primos, $\phi(100)$ = $\phi(5)$ $\times$ $\phi(5)$ $\times$ $\phi(2)$ $\times$ $\phi(2)$não é verdade porque os 2s não são primos e os 5s também não são primos.
Assim, $\phi(100)$ = $\phi(25)$ $\times$ $\phi(4)$.
$\phi(25)$ = 20 (podemos avaliar isso por meio da fórmula $\phi(p^n) = p^{n-1}(p-1)$, então $ \ phi (5 ^ 2) = 5 ^ {1} (4) = 5 \ vezes 4 = 20.
$ \ phi (4) $ = 2.
$ \ implica$$\phi(100)$ = $20 \times 2$ = 40.
Obrigado a @Arthur e @DreiCleaner por esclarecer isso, e a @JWTanner por sugerir algumas maneiras de tornar esta resposta melhor!
Conforme apontado nos comentários, $5$ e $5$não são coprime, então você não pode usar a regra do produto lá. Mesmo para$2$ e $2$. Eu sugiro simplesmente contar diretamente, já que envolve números pequenos.
Há, no entanto, também uma regra simples para $\phi(a^n)$ você pode usar, tanto nessa fase para $\phi(4)$ e $\phi(25)$, ou imediatamente para $100=10^2$. Se você ainda não viu essa regra, aqui está um pequeno indicador para você começar:
Quantos números de 0 a 10 são coprime a 10? Que tal de 10 a 20? Que tal de 20 a 30? E quanto a [e assim por diante ...]
Finalmente, há uma diferença entre ser coprime de 10 e coprime de 100?
Ok ... regra 1:
E se $p$ é primo $\phi(p) = p-1$. Isso deve ser claro como$1$ para $p-1$ são todos relativamente primos para $p$.
Regra 2:
E se $n = p^k$ então $\phi(p) = p^{k-1}(p-1)$.
Não tão óbvio no início, mas se você considerar todos os números entre $1$ e $p^k-1$ são da forma $q*p + r; 0\le r < p$ do que $p*p + r$ relativamente primo se um apenas se $r\ne 0$ e então números $q*p + 1, q*p+2, ....q*p+(n-1)$ são relativamente primos enquanto $q*p + 0$não é. Para cada$q$ há $p-1$ destes $q*p + r; r\ne 0$ e a questão permanece: quantos $q$estão lá? Bem,$q$ pode ser tão pouco quanto $0$ para $n=1,...., p-1$ e tão grande quanto $p^{k-2}$ para $p^{k-1} +1=p*p^{k-1}+1,.., $ para $p^k-1 = p*p{k-1} + (p-1)$. então há$p^{k-1}$ possível $q$se então há $(p-1)\times p^{k-1}$ ou $p^{k-1}(p-1)$ números relativamente primos para $p^k$.
A regra final é
regra 3: se $\gcd(a,b)=1$ então $\phi(ab) = \phi(a)\phi(b)$. Isso com as outras regras pode determinar$\phi(n)$ para todos os inteiros positivos $n$ considerando a fatoração principal de $n$. E se$n = \prod p_i^{k_i}$ então $\phi (n) = \prod \phi(p_i^{k_i}) = \prod( (p-1)p_i^{k_i-1})$.
assim $\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$.
Agora, a razão para a regra 3: é semelhante ao primeiro às regras, mas um pouco mais difícil de derivar. Mas isto pode ser feito.
Aqui está um argumento grosseiro :
De cada $a$ números $\phi(a)$ deles serão relativamente primos para $a$ e $(a-\phi(a))$ deles não.
Tão fora de $ab$ números $b\phi(a)$ do será relativamente principal para $a$ e $(ab - b\phi(a)$ não será.
De cada $b$ números $\phi(b)$ deles serão relativamente primos para $b$ e $(b-\phi(b))$ deles não.
Tão fora de $ab$ números $a\phi(b)$ do será relativamente principal para $a$ e $(ab - a\phi(b))$ não será.
E fora de $ab$ números $(b-\phi(b))(a-\phi(a))$não será relativamente principal para nenhum $a$ nem $b$.
Usando inclusão / exclusão
$\phi(ab) =$ o número de números relativamente primos para $ab$ Menor que $ab=$
o número de números que são relativamente primos para ambos $a$ e para $b=$
O número total de números até $ab$ menos os números que não são relativamente primos para $a$ menos o número que não é relativamente primo para $b$ mais (para evitar contagem dupla) os números que não são relativamente primos para nenhum $=$
$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.