Question

Sei f : N₀ x N₀ → N₀ gegeben durch f(k, l) = 2^k(2l + 1) - 1. Zeigen Sie, dass f bijektiv ist.

Comments

Injektiv ist klar. Bei der Surjektivität ist es vielleicht hilfreich:

eine natürliche Zahl n ≥ 1 kann eindeutig als produkt einer geraden Zweierpotenz die wären ja enthalten und einer ungeraden Zahl (hier ist das 2l + 1) geschrieben werden

---

mit gerade meinte ich dass eine Zweierpotenz eine gerade Zahl ist. Sonst würden ja verschiedene Elemente aus der Ausgangsmenge zu einem Element der Zielmenge führen und f wäre nicht injektiv.

Answer 1

Hallo gast2345, Beweis Injektivität:

Die Primfaktorenzerlegung ist eindeutig (I):
180 = 2² * 3² * 5
2² : 2^k
3² * 5 : Jedes Produkt aus ungeraden Zahlen ist wieder ungerade -> 2 l + 1

Ist jede ungerade Zahl 2 l + 1 eindeutig in Primzahlen zerlegbar?  Ja, siehe (I).  Damit ist f injektiv.  Es gibt für eine Zahl wie z. B. 180 keine zwei verschiedenen Paare (k, l), mit denen man diese Zahl bilden kann.

Bleibt Surjektivität zu zeigen.