Teilbarkeitsbeweise

Neue Frage »

Bjoern1982 Auf diesen Beitrag antworten »
Teilbarkeitsbeweise
Hallo

Ich poste einfach mal direkt alle 5 zu beweisenden Aussagen:

(1) mod 13

(2) Für jedes n aus gilt

(3) Welche ganze Zahlen x ungleich 3 erfüllen (x-3) | (x³-3)

(4) Eine Zahl ist genau dann durch 9 teilbar, wenn ihre Quersumme durch 9 teilbar ist

(5) Eine Zahl ist genau dann durch 11 teilbar, wenn ihre alternierende Quersumme durch 11 teilbar ist

So, fangen wir mal bei (1) an:

Ich habe durch Vorlesungen über Kryptologie Vorkenntnisse über den Satz von Euler, der sich hier z.B. prima anwenden lässt. Das war jedoch noch nicht dran in der Vorlesung und ich wäre an einer alternativen Lösung interessiert.
Achso Square and Multiply war auch noch nicht dran, damit gings ja auch.

Gruß Björn
AD Auf diesen Beitrag antworten »

Bei (1) werfe ich einfach mal nur in den Ring. Augenzwinkern
Bjoern1982 Auf diesen Beitrag antworten »

Hab schon erstaunlich lang drüber nachgedacht aber ich komm nicht drauf unglücklich

Soll ich zeigen, dass aus n | a²+b² folgt, dass gilt ?

Btw Aufgabe (2) konnte ich lösen.
tmo Auf diesen Beitrag antworten »

Setzen wir mal und .

Dann ist die Behauptung .

Im Allgemeinen gilt das nicht, man muss einfach mal in diesem Fall hier m = 2 wählen.

Aber man kann zeigen, dass es für ungerade m gilt. Wie gut, dass hier m = 35 ist Augenzwinkern

Oder als Spezialfall hier: Arthur Dent wollte vielleicht darauf hinaus, dass du berechnest. Natürlich ohne Garantie, ich kann ja keine Gedanken lesen Big Laugh
Bjoern1982 Auf diesen Beitrag antworten »

Achsooo, und ich dachte schon wie ich das allgemein für alle m zeigen soll.
Ok dann mal für ungerade m, also m=2k-1 und damit

k=1:

Das entspricht der Ausgangsbedingung und damit ist n in jedem Fall ein Teiler

Induktionsschritt k --> k+1



Ob 2k-1 oder 2k+1 ist ja egal und es bleibt somit bei dem ungeraden Faktor im Exponenten und damit auch dabei, dass n ein Teiler dafür sein muss.

Alles korrekt ?

Danke tmo für den Hinweis smile

Was meinst du hiermit bzw wie sollte mir das helfen ?

Zitat:
Arthur Dent wollte vielleicht darauf hinaus, dass du berechnest


Gruß Björn
Bjoern1982 Auf diesen Beitrag antworten »

Gedanken zu (3)

Polynomdivision:

(x³-3) : (x-3)=x²+3x+9+(24/(x-3))

Jetzt einfach nur gucken wann der letzte Summand ganzzahlig wird oder ?

Also für x aus {-21,-9,-5,-3,-1,0,1,2,4,5,6,7,9,11,15,27}

Einverstanden ?
 
 
WebFritzi Auf diesen Beitrag antworten »

Zitat:
Original von Bjoern1982
Was meinst du hiermit bzw wie sollte mir das helfen ?

Zitat:
Arthur Dent wollte vielleicht darauf hinaus, dass du berechnest



Huups, hatte gar nicht gesehen, dass deine Induktion nicht in Ordnung ist. Folgendes ist eine "Komplettlösung" für deine obige Frage. Wenn du sie sehen willst, machst du die erste eckige zu einer geschweiften Klammer. Aber da du ja Björn bist, möchtest du das wahrscheinlich gar nicht. Augenzwinkern



Deine Induktion ist falsch, da es eben nicht egal ist, ob 2k + 1 oder 2k - 1. Für 2k - 1 ist die Behauptung nach Induktionsvoraussetzung wahr. Für 2k + 1 musst du sie noch zeigen. Das ist aber gar nicht so schwer und um einiges einfacher als die obige "Musterlösung". Das zusätzliche Quadrat im Exponenten spielt übrigens keine Rolle. Du kannst es überall weglassen.
ajax2leet Auf diesen Beitrag antworten »

Zitat:
Original von WebFritzi
Das zusätzliche Quadrat im Exponenten spielt übrigens keine Rolle. Du kannst es überall weglassen.


Bist du dir da sicher?
So wie ich das sehe, gilt die Gleichung nicht für Exponenten der Form 2k+1 verwirrt
Am Beispiel k=1: 8 + 27 = 35
Bei mir klappt die Induktion tatsächlich nur für Exponenten in der Form 2(2k + 1)

Oder meintest du das anders?
Bjoern1982 Auf diesen Beitrag antworten »

@ WebFritzi

Zitat:
Folgendes ist eine "Komplettlösung" für deine obige Frage. Wenn du sie sehen willst, machst du die erste eckige zu einer geschweiften Klammer.


Worauf beziehst du dich genau ? Ich kann es beim besten Willen nicht sehen und bei mir wird auch nichts falsch angezeigt oder so verwirrt

Gruß Björn
AD Auf diesen Beitrag antworten »

Zitat:
Original von tmo
Arthur Dent wollte vielleicht darauf hinaus, dass du berechnest.

Ganz gewiss nicht - womit dann bewiesen wäre, dass du keine Gedanken lesen kannst. Augenzwinkern

Es gibt natürlich viele Wege, um die Teilbarkeit von durch im Falle ungerader m zu zeigen. Mit Modulrechnung kann man es z.B. auch schlicht so tun:



Die vorletzte Gleichheit ist natürlich die, wo man die Ungeradheit von nutzt.
Bjoern1982 Auf diesen Beitrag antworten »

Mit Modulorechnung geht es in der Tat um einiges schneller smile

Kann noch jemand einen Kommentar zu meiner Lösung durch Induktion bzw meiner Lösung zu (3) abgeben ?
AD Auf diesen Beitrag antworten »

Zitat:
Original von Bjoern1982
Induktionsschritt k --> k+1



Ob 2k-1 oder 2k+1 ist ja egal und es bleibt somit bei dem ungeraden Faktor im Exponenten und damit auch dabei, dass n ein Teiler dafür sein muss.

Diese Logik bleibt mir vollständig verschlossen. unglücklich


Aber die Lösung zu (3) ist voll und ganz richtig. Hättest nur noch deutlicher erwähnen können, dass dort die ganzzahligen Teiler von 24 durchläuft.
WebFritzi Auf diesen Beitrag antworten »

Zitat:
Original von Bjoern1982
Kann noch jemand einen Kommentar zu meiner Lösung durch Induktion [...] abgeben ?


Du liest wohl meine Beitraege nicht ordentlich. unglücklich

Und steht bei dir in meinem letzten Beitrag keine LaTeX-Fehlermeldung "Missing { inserted"?


@ajax: Ja, ich bin mir ganz sicher. Augenzwinkern
ajax2leet Auf diesen Beitrag antworten »

Zur Induktion:

Zu zeigen



Wichtig ist jetzt, dass
Bjoern1982 Auf diesen Beitrag antworten »

@ WebFritzi

Tut mir leid, jetzt hab auch ichs verstanden wie du das meintest Augenzwinkern

Ich schau es mir später in Ruhe an, bin jetzt erstmal weg.

@ ajax

Auch den Beitrag von dir schaue ich mir heute Nacht in Ruhe an, dank dir.

Björn
WebFritzi Auf diesen Beitrag antworten »

Die Induktion (ok, der -schritt Augenzwinkern ) ist ein Einzeiler:

Sei (Induktionsvoraussetzung)



Dann folgt




EDIT: OK, jetzt kann ich ja auch meine "Musterloesung" posten:

ajax2leet Auf diesen Beitrag antworten »

Jetzt verstehe ich auch, was du meintest. Ist einfach ein anderer Ansatz Gott
WebFritzi Auf diesen Beitrag antworten »

Es ist kein anderer Ansatz, sondern eine Verallgemeinerung. Die Behauptung gilt halt nicht nur fuer Quadratzahlen, sondern fuer alle natuerlichen Zahlen.
Bjoern1982 Auf diesen Beitrag antworten »

Danke an alle, eure Lösungswege habe ich jetzt nachvollziehen können.

@ WebFritzi

Lösung durch Umformen zu einer (endlichen) geometrischen Reihe - nicht schlecht smile

Auch auf die Gefahr hin mich zu blamieren aber ich hake nochmal nach wegen

Zitat:
Induktionsschritt k --> k+1



Ob 2k-1 oder 2k+1 ist ja egal und es bleibt somit bei dem ungeraden Faktor im Exponenten und damit auch dabei, dass n ein Teiler dafür sein muss.


Dieser Gedankengang ist euch ja ein Dorn im Auge, ich verstehe allerdings immer noch nicht so richtig warum. In der Induktionsvoraussetzung steht 2k-1 im Exponenten und im Induktionsschritt taucht nun 2k+1 auf. Es werden doch hagenau dieselben Exponten durchlaufen, denn ob ich eine ungerade Zahl jetz durch 2k-1 oder 2k+1 darstelle ist doch egal. Und demnach ist es in meinen Augen eigentlich trivial dass n damit auch ein Teiler von sein muss Erstaunt1

Gruß Björn
WebFritzi Auf diesen Beitrag antworten »

Offenbar hast du das Prinzip der vollst. Induktion noch nicht ganz verstanden. In der Induktionsvoraussetzung wird angenommen, dass die Behauptung für ein k gilt. Im Induktionsschritt musst du damit zeigen, dass sie auch für k+1 gilt.

Also,

Induktionsvoraussetzung: Beh. gilt mit Exponenten 2k - 1
Induktionsbehauptung: Beh. gilt auch mit Exponenten 2(k+1) -1 = 2k + 1.
Bjoern1982 Auf diesen Beitrag antworten »

Naja komplett falsch verstanden glaub ich nicht, aber zumindest die falsche Behauptung am Ende benutzt Augenzwinkern Danke für den Hinweis.

So dann bleiben noch die beiden Aufgaben:

Zitat:
(4) Eine Zahl ist genau dann durch 9 teilbar, wenn ihre Quersumme durch 9 teilbar ist

(5) Eine Zahl ist genau dann durch 11 teilbar, wenn ihre alternierende Quersumme durch 11 teilbar ist


Die Idee, die hinter dem Beweis steckt habe ich mir schon anhand eines Beispiels klargemacht, es geht ja bei (4) und (5) nach derselben Idee oder ?

Also nehmen wir mal die Zahl z=27315 und zerlegen sie folgendermaßen:

2*10000+7*1000+3*100+1*10+5

2*(9999+1)+7*(999+1)+3*(99+1)+1*(9+1)+5

9(2*1111+7*111+3*11+1*1)+(2+7+3+1+5)

Der 1. Summand ist offensichtlich durch 9 teilbar und damit muss der 2. Summand, welcher gerade die Quersumme QS(z) darstellt, auch durch 9 teilbar sein, damit z durch 9 teilbar ist.

Nun muss ich das ja allgemein fomulieren:





Die mittlere Summe ist offensichtlich kongruent 0 mod 9, also durch 9 ohne Rest teilbar (bzw kann man sogar sagen dass sie ganz wegfällt wenn man modulo 9 rechnet ?) Damit muss dann die letzte Summe, welche gerade QS(z) darstellt, durch 9 teilbar sein, damit z durch 9 teilbar ist.

Kann man das so lassen oder ist es noch etwas schlampig bzw unvollständig ?

Für (5) würde ich es dann einfach analog machen:



Die mittlere Summe ist hier auch wiederum kongruent 0 mod 11, denn für alle i=2r mit r aus IN_0 entsteht 1-1=0 und für alle i=2s-1 mit s aus IN entsteht (-1)-(-1)=0 bei der Modulorechnung bei

Ist das so in Ordnung ?
AD Auf diesen Beitrag antworten »

Ja, ist in Ordnung.
Bjoern1982 Auf diesen Beitrag antworten »

Dank dir smile
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »