Use que varphi(x y)=varphi(x) varphi(y) quando (x, y)=1 para provar que:
m=underbraceP1^alpha1 cdot P2^alpha2 cdot ldots cdot Pn^alphanc decomposição em fatores primos Rightarrow varphi(m)=prodi=1^n Pi^alphai-1(Pi-1) çã

Passo 1

Beleza! A questão pede pra gente provar que, se temos um número m = P1^alpha1 cdot P2^alpha2 cdot ldots cdot Pn^alphan, decomposto em fatores primos da forma
então a função de Euler pode ser calculada multiplicando termos como para cada primo que compõe . Vamos usar a propriedade de que quando e são primos entre si.

Passo 2

Primeiro, vamos lembrar o que é a função de Euler . Ela conta quantos números menores que são coprimos com (ou seja, que não têm nenhum divisor comum com além de 1). Uma propriedade importante dessa função é que ela é multiplicativa para números que são primos entre si. Isso significa que se dois números e não têm fatores primos em comum, então .

Passo 3

Como varphi(m) = varphi(P1^alpha1) cdot varphi(P2^alpha2) cdot ldots cdot varphi(Pn^alphan) está decomposto em fatores primos diferentes (cada é primo e distintos entre si), podemos aplicar a propriedade multiplicativa da função . Ou seja,

Passo 4

Agora, precisamos calcular varphi(p^alpha) = p^alpha - p^alpha - 1 = p^alpha - 1(p - 1) para cada . Sabemos que se é um número primo e é um expoente positivo, então
Isso ocorre porque de números, exatamente são múltiplos de e, portanto, não são coprimos com .

Passo 5

Substituindo essa expressão na fórmula multiplicativa que montamos no Passo 3, temos:
varphi(m) = prodi=1^n varphi(Pi^alphai) = prodi=1^n Pi^alphai - 1(Pi - 1)

Resposta

Portanto, provamos que
varphi(m) = prodi=1^n Pi^alphai - 1(Pi - 1)

Exercícios relacionados

Calcule varphi(n) para n=1,2, ldots, 20 e varphi(347), varphi(312).
Mostre que varphi(2 n)=lvarphi(n), se n é ímpar 2 varphi(n), se n é par éíé.
Encontre todos os geradores do grupo (Z48,+).
Encontre todos os elementos invertíveis de Z12 em relação a multiplicação. Justifique.