Zeige das (32|33^(333)-1) gilt.

Question

Aufgabe:

Zeige das (32|33^(333)-1) gilt. Also 33 teilt 33^(333)-1. Das soll keine Rechenaufgabe sein.

Problem/Ansatz

Mein bisheriges Vorgehen:

Ich gehe von der Teilbarkeit aus dann muss es ein k aus den ganzen Zahlen geben sodass gilt:

32×k=33³³³-1

Das kann ich ja auch umformulieren zu

(33-1)×k=33³³³-1

Nun habe ich ja auf beiden Seiten die gleiche Darstellungsform hinbekommen. Aber welcher Schritt ist jetzt sinnvoll damit ich das oben genannte Zeigen kann.

In unserer VL geht es um die Zahlentheorie in den ganzen Zahlen daher wäre eine Division jetzt unpassenden.

Comments

Benutze vst. Ind. oder geom. Reihe.

---

Also angenommen eine Division wäre erlaubt. Dann könnte ich meine Gleichung doch in die Form (33-1)¹×k=(33-1)³³³ zu k=(33-1)³³² umformen. Somit ex. Doch das k und auch das 32 die 33³³³-1 teilt.

---

Dann könnte ich meine Gleichung doch in die Form (33-1)1×k=(33-1)333 zu k=(33-1)332 umformen.

Nein - das kannst Du nicht, da $33^{333}-1 \ne (33-1)^{333}$

Answer 1

Hallo rado,

ersetze die $33$ durch die Summe $(32 + 1)$ und wende den binomischen Lehrsatz an:$$(32+1)^n = \sum\limits_{k=0}^n {n \choose k} 32^{n-k} \cdot 1^k$$wobei es hier auch keine Rolle spielt, wie groß das $n$ ist. In dieser Summe mit $n+1$ Summanden ist jeder Summand bis auf einen(!) durch $32$ teilbar (welcher?).

Also gilt für jedes $n \in \mathbb N_0$$$(32+1)^n \equiv 1^n = 1 \mod 32$$und wenn man von diesem Ausdruck $1$ abzieht, so ist das Resultat durch $32$ teilbar!

Man kann es natürlich auch über vollständige Induktion beweisen oder mit der Formel für die endliche geometrische Reihe. Muss man aber nicht ;-)

Gruß Werner

Comments

Vielen Dank für die Antwort. Das ist für mich stimmig. Jedoch dürfen wir zum lösen unserer Aufgabn nur Behandeltes aus der VL nutzen. Da wäre max. Induktion erlaubt. Da es sich aber nicht um einen Beweis handelt sondern nur dass wir es zeigen sollen würde ich meine kommentierte Frage aus dem 1 Post auch hier einmal stellen.

Also angenommen eine Division wäre erlaubt. Dann könnte ich meine Gleichung doch in die Form (33-1)1×k=(33-1)333 zu k=(33-1)332 umformen. Somit ex. Doch das k und auch das 32 die 33333-1 teilt.

---

Vlt. Um das zu konkretisieren: Definiert ist folgendes:

a|b wenn es eine ganze Zahl k gibt sodass gilt a×k=b

---

Wie würde ich denn mit vollständiger Induktion vorgehen?

---

Da wäre max. Induktion erlaubt. Da es sich aber nicht um einen Beweis handelt sondern nur dass wir es zeigen sollen ...

"Zeigen" und "Beweis" ist nicht so verschieden. Und man kann es auch hier mit v.I. sehr gut 'zeigen'. Induktionsanfang wäre $$n=1 \implies 32 \mid 33^1 - 1 \space \checkmark$$... und ist erfüllt, Und der Schritt von $n$ nach $n+1$ geht so:$$\begin{aligned} 33^{n+1} -1 &= 33\cdot 33^n - 1 \\ &= 32 \cdot 33^n + 1\cdot 33^n - 1 \\ &= 32 \cdot 33^n + \underbrace{33^n - 1}_{32\mid 33^n-1} \\ &= 32 \cdot 33^n + 32k && k \in \mathbb N \\ &= 32(33^n +k) \end{aligned}$$Daraus folgt dann$$32\mid 33^n-1 \quad n \in \mathbb N$$ und damit gilt das auch für $n=333$.

... würde ich meine kommentierte Frage aus dem 1 Post auch hier einmal stellen.

hatte ich oben schon kommentiert.

---

Oh super! Vielen Dank.

---

Vlt. Um das zu konkretisieren: Definiert ist folgendes:
a|b wenn es eine ganze Zahl k gibt sodass gilt a×k=b

Ja natürlich. Man kann sich aber trotzdem überlegen, was bei $(a+b)^n$ so geschieht.$$(a+b)^2 =a^2+2ab + b^2 = a(a+2b) + b^2$$kennst Du doch.

Wenn man dies nochmal mit $(a+b)$ multipliziert, geht das so weiter:$$\phantom{=}(a(a+2b) + b^2)(a+b) \\= a(a(a+2b) + b^2) + ab(a+2b) + b^3 \\= ak + b^3 \quad\quad k \in\mathbb N$$So kommt man doch recht fix drauf, dass dies gilt$$(a+b)^n = ak + b^n \quad k,\,n \in\mathbb N$$Wenn nun die Teilbarkeit durch $a$ eine Rolle spielt, muss man sich nur noch das $b^n$ am Ende anschauen.

---

Da für die natürliche Zahl $k = \sum\limits_{n=0}^{332}{33^n}$ gilt, dass $k = \frac{33^{333}-1 }{33-1}$ ist, folgt die Behauptung unmittelbar.

Man kann es natürlich auch über vollständige Induktion beweisen oder mit dem Binomischen Satz. Muss man aber nicht ;-)