Doze dos números abaixo de 36 não compartilham nenhum fator com ele

A função φ de Euler como produto sobre primos, e os mesmos 12 por inclusão–exclusão em uma linha.

Aritmética e funções · Nível: Resultado clássico · Atualizado em 2026-11-10

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.

Este é um site de ferramentas independente de terceiros. Não é afiliado à Casio, à Texas Instruments nem aos seus distribuidores, e não conta com patrocínio ou autorização deles. Os nomes de modelos e produtos são marcas comerciais de seus respectivos titulares e aparecem aqui apenas para identificar os dispositivos.

As sequências de teclas destes manuais foram redigidas a partir dos próprios dados de layout deste site — os mesmos que a calculadora online renderiza — junto com informações de produto disponíveis publicamente. As especificações e as configurações regionais são verificadas no dispositivo físico e no material mais recente do fabricante.