Natürliche Zahlen/Primfaktoren/Äquivalenzrelation/Aufgabe/Lösung

  1. Die Reflexivität ist klar, da die erste Potenz teilt. Die Symmetrie ist von der Formulierung her klar. Zum Nachweis der Transitivität sei und . Dann ist ein Teiler von für ein gewisses und ist ein Teiler von für ein gewisses . Dann ist

    und

    und daraus folgt

    so dass eine Potenz von teilt. Die umgekehrte Teilbarkeitsbeziehung ergibt sich genauso.

  2. Es ist offenbar (es kommen jeweils die Primfaktoren und vor) und , darüber hinaus sind und nur zu sich selbst äquivalent. Dies ergibt sich aus der Charakterisierung der Relation mit Primteilern aus dem folgenden Teil.
  3. Wir betrachten die Abbildung

    die einer natürlichen Zahl die Menge der in der Primfaktorzerlegung von vorkommenden Primzahlen zuordnet. Es sei . Da in einer Potenz (zu einem positiven Exponenten) die gleichen Primfaktoren vorkommen (nur ihre Vielfachheit ändert sich) folgt aus der Eigenschaft, dass eine Potenz von teilt, dass die Primteiler von in den Primteilern von enthalten sein müssen. Aus folgt also, dass die Primteiler der beiden Zahlen überhaupt gleich sind. Nach Fakt gibt es daher eine zugehörige Abbildung

    Diese ist injektiv, da wenn von und die Primteiler übereinstimmen, dann eine hinreichend große Potenz von teilt und umgekehrt. Diese Abbildung ist nicht surjektiv, da nur endliche Teilmengen der Primzahlen im Bild liegen, es aber unendlich viele Primzahlen gibt.

  4. Ein Repräsentantensystem besteht aus allen natürlichen Zahlen mit der Eigenschaft, dass sämtliche Exponenten in ihrer Primfaktorzerlegung gleich sind.