Il conteggio dei numeri interi fino a 36 che non hanno fattori in comune con esso è 12. La ricetta del prodotto prende 36 e scarta le frazioni divisibili per ogni fattore primo: moltiplica per (1 − 1/2) per eliminare i pari, per (1 − 1/3) per eliminare i multipli di tre, e il banco di lavoro stampa 12. Dato che 36 = 2²·3², quei due primi sono gli unici che possono essere condivisi.
Il secondo link conta la stessa cosa nell'altro modo, per inclusione ed esclusione: diciotto multipli di 2, dodici multipli di 3, e i sei multipli di 6 sottratti due volte quindi riaggiunti una volta: 36 − 18 − 12 + 6 = 12. Le due ricette devono concordare, e il motivo per cui lo fanno è che «divisibile per 2 o 3» è esattamente «non coprimo con 36». φ è il numero su cui gira l'aritmetica RSA: il teorema di Eulero dice a^φ(n) ≡ 1 (mod n) per ogni a coprimo con n, quindi la dimensione di questo conteggio è la dimensione del ciclo.
Risposta
12
Come leggerla
36·(1 − 1/2)(1 − 1/3) sul banco di lavoro. Il secondo link è il conteggio per inclusione–esclusione, e il terzo è la fattorizzazione 2²·3² che dice quali primi contano.
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
Svolgilo nella calcolatrice
Questi link aprono la calcolatrice giusta con i numeri di questo problema già digitati. La riga sopra è ciò che lo schermo dovrebbe mostrare — verifica tu stesso.