Die Zahl der ganzen Zahlen bis 36, die keinen gemeinsamen Faktor mit ihr haben, ist 12. Das Produktrezept nimmt 36 und wirft die Bruchteile weg, die durch jeden Primfaktor teilbar sind: Multiplizieren Sie mit (1 − 1/2), um die geraden Zahlen zu entfernen, mit (1 − 1/3), um die Vielfachen von drei zu entfernen, und der Rechner zeigt 12. Da 36 = 2²·3² ist, sind diese beiden Primzahlen die einzigen, die man teilen kann.
Der zweite Link zählt dasselbe auf die andere Weise, durch Inklusion und Exklusion: achtzehn Vielfache von 2, zwölf Vielfache von 3 und die sechs Vielfachen von 6, die zweimal subtrahiert und deshalb einmal wieder addiert werden – 36 − 18 − 12 + 6 = 12. Die beiden Rezepte müssen übereinstimmen, und der Grund, warum sie es tun, ist, dass „durch 2 oder 3 teilbar“ genau „nicht teilerfremd zu 36“ ist. φ ist die Zahl, auf der die RSA-Arithmetik läuft: Der Satz von Euler sagt a^φ(n) ≡ 1 (mod n) für jedes zu n teilerfremde a, die Größe dieser Zählung ist also die Größe des Zyklus.
Antwort
12
So lesen Sie sie
36·(1 − 1/2)(1 − 1/3) auf dem Rechner. Der zweite Link ist die Inklusion-Exklusion-Zählung, und der dritte ist die Faktorisierung 2²·3², die sagt, welche Primzahlen zählen.
Quelle
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
Im Rechner durchrechnen
Diese Links öffnen den passenden Rechner mit den bereits eingegebenen Zahlen dieser Aufgabe. Die Zeile darüber ist das, was der Bildschirm anzeigen sollte – prüfen Sie selbst.