Zwölf der Zahlen unter 36 teilen keinen Faktor mit ihr

Eulers φ-Funktion als Produkt über Primzahlen, und dieselben 12 durch Inklusion-Exklusion in einer Zeile.

Arithmetik und Funktionen · Niveau: Klassisches Ergebnis · Aktualisiert am 2026-11-10

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.

Dies ist eine unabhängige Tool-Website eines Drittanbieters. Sie ist weder mit Casio, Texas Instruments oder deren Vertriebspartnern verbunden noch von ihnen gesponsert oder autorisiert. Modell- und Produktnamen sind Marken der jeweiligen Inhaber und erscheinen hier nur zur Identifizierung der Geräte.

Die Tastenfolgen in diesen Handbüchern wurden aus den eigenen Layoutdaten dieser Website erstellt — denselben Daten, die der Online-Rechner darstellt — sowie aus öffentlich verfügbaren Produktinformationen. Spezifikationen und regionale Konfigurationen werden am physischen Gerät und anhand der neuesten Unterlagen des Herstellers überprüft.