Zeige jede natürliche Zahl ist ein Faktor einer Summe aufeinanderfolgender Zweierpotenzen

Question

Aufgabe:

Ich versuche zu beweisen, dass jede natürliche Zahl ein Faktor ist von einer Summe aufeinanderfolgender Zweierpotenzen. Das heißt also, es existieren l,k ∈ ℕ sodass n | 2^l+1+2^l+2+...+2^l+k , für jedes n ∈ ℕ.

Problem/Ansatz:

Ich weiß, dass es nicht schwierig ist zu beweisen, dass jede natürliche Zahl darstellbar ist als eine Summe von irgendwelchen Zweierpotenzen. Aber ist dies relevant für diese Aussage?

Gibt es einen einfachen Weg dies zu beweisen?

Leider weiß ich nicht so ganz, wie man hier vorgehen sollte.

Comments

Es existieren l,k ∈ ℕ sodass n | 2^l+1+2^l+2+...+2^l+k , für jedes n ∈ ℕ.

Nein!

Es existieren l,k ∈ ℕ∪{0} sodass n | 2^l+1+2^l+2+...+2^l+k , für jedes n ∈ ℕ.

---

n | n*2^0

würde ich sagen.

---

das wäre einfach, aber ich will zeigen dass es wirklich für l,k ∈ ℕ gilt

---

Es ist doch \(l=k=0\in\mathbb{N}\) und die Summe hat eben nur einen Summanden.

---

mit ℕ hätte ich eigentlich nur alle positiven ganzen Zahlen gemeint

---

Du willst beweisen, dass jede natürliche Zahl Faktor einer Summe aufeinanderfolgender Zweierpotenzen ist.

Jede natürliche Zahl Faktor ist bereits selbst Summe aufeinanderfolgender Zweierpotenzen (d.h.: sie besitzt eine binäre Darstellung).

---

aber bei der Binärdarstellung hat man Einsen und Nullen, das wären ja dann keine aufeinanderfolgenden Zweierpotenzen

---

Es reicht nachzuweisen, dass es für jede ungerade Zahl u eine Zahl n gibt, so dass u | 2^n - 1

---

syntax-sorcerer, du hast natürlich recht.

---

hj2166 Könntest du mir diese Vorgehensweise genauer erklären?

---

Jede natürliche Zahl m lässt sich eindeutig in der Form m = u·2^v mit einer ungeraden Zahl u und einer natürlichen Zahl v schreiben. Außerdem ist dein 2^l+1 + 2^l+2 + ... + 2^l+k = 2^l+1·(2^0+2^1+ ... +2^k-1) = 2^l+1·(2^k - 1)

Man betrachte z.B. m = 440 und findet l=2 und k=20 , denn
440 = 55·8 = 55·2^3 , 55·19065 = 2^20 - 1 = 1 + 2 + 4 + ... + 2^19
also gilt 440 | 2^3 + 2^4 + ... + 2^22

---

Aus Interesse, wo ist das Problem her? Die einzige Lösung, die mir eingefallen ist, war ziemlich "per Hand" und mir fielen keine coolen Vorlesungslemmata zum Anwenden ein. Also das Problem fand ich cool, nur in einem Übungszettel hätte ich die Aufgabe als Ersti gehasst.

---

@hj2166 danke, das hilft mir weiter

@joners mein Professor hat uns das problem auf den übungszettel draufgetan...bin im 2.semester

---

Ok ich glaub ich hab den Beweis jetzt verstanden!

Answer 1

Sehr schöne Kopfnuss, hat mir ein schönes Frühstück bereitet!

Zuerst einmal siehe, dass (leicht andere Notation, fand ich so einfacher) für \(0\leq l\leq j\) mittels Teleskopsumme über geometrische Summen der Zweierpotenzen:

\(2^{l}+\ldots + 2^{j}=(2^{j+1}-1)-(2^{l}-1) = 2^{l}(2^{j-l+1}-1)\).

Wenn wir uns das anschauen, merken wir: Wenn unsere Zahl \(m\) den Faktor \(2\) sagen wir mal \(i\) mal hat, dann können wir den in dem Produkt ganz rechts bei \(i=l\) verbauen. Es reicht also zu zeigen, dass jede ungerade Zahl Teiler eines \(2^{k}-1\) ist, für \(k\geq 1\).

Wir betrachten jetzt die Folge \(a_n\in \mathbb{Z}_{m}\) gegeben durch \(a_n\equiv 2^n-1\text{ mod }m\). Die Folge \(a_n\) ist eine echte Folge (hat unendlich viele Folgenglieder), kann aber nur endlich viele Werte annehmen, es gibt also nach dem Schubfachprinzip solche \(k_1<k_2\) mit \(a_{k_1}\equiv a_{k_2}\) bzw. \(a_{k_2}-a_{k_1}\equiv 0\).

Anders gesagt: Es gibt \(k_1<k_2\), sodass \((2^{k_2}-1)-(2^{k_1}-1)=2^{k_1}(2^{k_2-k_1}-1)\) ein Vielfaches von \(m\) ist. Da \(m\) ungerade ist, muss der rechte Faktor \((2^{k_2-k_1}-1)\) ein Vielfaches von \(m\) sein, mit \(k_2-k_1\geq 1\), was die Behauptung beweist.

Comments

Der zweite Teil vielleicht etwas eleganter:

Wir betrachten das Element \(g=[2]\) in der Gruppe \(\mathbb{Z}_m^\ast\) (es gilt \(g\in\mathbb{Z}_m^\ast\) da nach Annahme \(2\) und \(m\) teilerfremd sind). Da \(\mathbb{Z}_m^\ast\) endlich ist, hat \(g\) endliche Ordnung, es gibt also ein \(k\) mit \(g^k=e\), in anderen Worten \(2^k\equiv 1\text{ mod }m\), oder \(2^k-1\equiv 0\text{ mod }m\).

Der Beweis ist etwas kürzer, und sagt sogar, wie man das \(k\) findet (einfach die Ordnung von \([2]\) in \(\mathbb{Z}_m^\ast\) berechnen!). Mit diesen Informationen kann man \(i\) und \(j\) direkt algorithmisch angeben.

---

for m in range(100):
  m = 2*m+1
  n = 1
  while (2**n-1)%m > 0:
      n += 1
  print(m,2**n-1)

Ein kurzes Programm, dass die Werte berechnet; bei m = 197 ist 2**n-1 30-stellig.

---

Vielen Dank für deine Ausarbeitung!

Könntest du mir da noch erklären wie genau man darauf schließen kann, dass m | 2^l(2^j-l+1-1) falls m gerade ist?

---

Garnicht^^ Das ist keine Fallunterscheidung im Sinne von "Fall 1: m ist gerade. Fall 2: m ist ungerade" sondern: Stell dir vor du hast m = 20 = 2*2*5. Dann kannst du l=2 wählen und hast als linken Faktor schon ne 4 stehen, du musst also nur sichergehen, dass 5 ein Teiler des rechten Faktors ist. Du kannst das l ja frei wählen, du sorgst also durch groß genügendes l einfach nur dafür, dass alle Zweien, die m als Teiler hat, durch den linken Faktor schon "bedient" sind.

---

Ok danke dir, dann verstehe ich jetzt wenigstens schon mal den 1. Teil!

Könntest du vielleicht noch etwas detaillierter erklären, wie das mit der Folge funktioniert?

---

Also kann man das einfach annehmen, dass \(a_n\equiv 2^n-1\text{ mod }m\) gilt ?