El recuento de números enteros hasta 36 que no tienen ningún factor en común con él es 12. La receta del producto toma 36 y descarta las fracciones divisibles por cada factor primo: multiplica por (1 − 1/2) para quitar los pares, por (1 − 1/3) para quitar los múltiplos de tres, y el banco de trabajo imprime 12. Como 36 = 2²·3², esos dos primos son los únicos que se pueden compartir.
El segundo enlace cuenta lo mismo de otra manera, por inclusión y exclusión: dieciocho múltiplos de 2, doce múltiplos de 3, y los seis múltiplos de 6 restados dos veces y por eso sumados de vuelta una —36 − 18 − 12 + 6 = 12—. Las dos recetas tienen que coincidir, y la razón por la que lo hacen es que «divisible por 2 o por 3» es exactamente «no coprimo con 36». φ es el número sobre el que funciona la aritmética de RSA: el teorema de Euler dice que a^φ(n) ≡ 1 (mod n) para todo a coprimo con n, así que el tamaño de este recuento es el tamaño del ciclo.
Respuesta
12
Cómo leerla
36·(1 − 1/2)(1 − 1/3) en el banco de trabajo. El segundo enlace es el recuento por inclusión–exclusión, y el tercero es la factorización 2²·3² que dice qué primos importan.
Fuente
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
Resuélvelo en la calculadora
Estos enlaces abren la calculadora adecuada con los números de este problema ya escritos. La línea de arriba es lo que debería mostrar la pantalla: compruébalo tú mismo.