Dodici dei numeri sotto 36 non condividono alcun fattore con esso

La totiente di Eulero come prodotto sui primi, e lo stesso 12 per inclusione–esclusione in una riga.

Aritmetica e funzioni · Livello: Risultato classico · Aggiornato il 2026-11-10

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.

Questo è un sito di strumenti indipendente di terze parti. Non è affiliato, sponsorizzato né autorizzato da Casio, Texas Instruments o dai loro distributori. I nomi dei modelli e dei prodotti sono marchi dei rispettivi proprietari e compaiono qui solo per identificare i dispositivi.

Le sequenze di tasti in questi manuali sono state scritte a partire dai dati di layout propri di questo sito — gli stessi che usa la calcolatrice online — insieme a informazioni sul prodotto disponibili pubblicamente. Le specifiche e le configurazioni regionali sono verificate sul dispositivo fisico e sulla documentazione più recente del produttore.