A contagem de números inteiros até 36 que não têm nenhum fator em comum com ele é 12. A receita do produto toma 36 e descarta as frações divisíveis por cada fator primo: multiplique por (1 − 1/2) para tirar os pares, por (1 − 1/3) para tirar os múltiplos de três, e a área de trabalho imprime 12. Como 36 = 2²·3², esses dois primos são os únicos que se podem compartilhar.
O segundo link conta o mesmo de outra maneira, por inclusão e exclusão: dezoito múltiplos de 2, doze múltiplos de 3, e os seis múltiplos de 6 subtraídos duas vezes e por isso somados de volta uma — 36 − 18 − 12 + 6 = 12. As duas receitas têm que coincidir, e a razão pela qual coincidem é que “divisível por 2 ou por 3” é exatamente “não coprimo com 36”. φ é o número sobre o qual funciona a aritmética do RSA: o teorema de Euler diz que a^φ(n) ≡ 1 (mod n) para todo a coprimo com n, então o tamanho desta contagem é o tamanho do ciclo.
Resposta
12
Como ler
36·(1 − 1/2)(1 − 1/3) na área de trabalho. O segundo link é a contagem por inclusão–exclusão, e o terceiro é a fatoração 2²·3² que diz quais primos importam.
Fonte
Euler's totient φ(36) = 36(1 − 1/2)(1 − 1/3) = 12, from his 1763 memoir on the function; the product form φ(n) = n·∏(1 − 1/p) over the primes dividing n is the standard result behind RSA key arithmetic
Resolva na calculadora
Estes links abrem a calculadora adequada com os números deste problema já escritos. A linha de cima é o que a tela deveria mostrar: confira você mesmo.