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

1. Die Reflexivität ist klar, da ${}n$ die erste Potenz ${}n=n^{1}$ teilt. Die Symmetrie ist von der Formulierung her klar. Zum Nachweis der Transitivität sei ${}\ell \sim m$ und ${}m\sim n$. Dann ist ${}\ell$ ein Teiler von ${}m^{r}$ für ein gewisses ${}r\in \mathbb {N}$ und ${}m$ ist ein Teiler von ${}n^{s}$ für ein gewisses ${}s\in \mathbb {N}$. Dann ist

   ${}\ell a=m^{r}\,$

   und

   ${}mb=n^{s}\,$

   und daraus folgt

   ${}\ell ab^{r}=m^{r}b^{r}=(mb)^{r}={\left(n^{s}\right)}^{r}=n^{sr}\,,$

   sodass ${}\ell$ eine Potenz von ${}n$ teilt. Die umgekehrte Teilbarkeitsbeziehung ergibt sich genauso.

2. Es ist offenbar ${}10\sim 100\sim 1000\sim 500$ (es kommen jeweils die Primfaktoren ${}2$ und ${}5$ vor) und ${}9\sim 27=3^{3}$, darüber hinaus sind ${}125=5^{3}$ und ${}210=2\cdot 3\cdot 5\cdot 7$ nur zu sich selbst äquivalent. Dies ergibt sich aus der Charakterisierung der Relation mit Primteilern aus dem folgenden Teil.
3. Wir betrachten die Abbildung

   $\varphi \colon \mathbb {N} _{+}\longrightarrow {\mathfrak {P}}\,({\mathbb {P} }),\,n\longmapsto \{{\text{Primteiler von }}n\},$

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

   ${\tilde {\varphi }}\colon Q\longrightarrow {\mathfrak {P}}\,({\mathbb {P} }).$

   Diese ist injektiv, da wenn von ${}m$ und ${}n$ die Primteiler übereinstimmen, dann ${}m$ eine hinreichend große Potenz von ${}n$ 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 ${}1$ sind.

Zur gelösten Aufgabe