Teilbarkeitsbeweise |
20.10.2008, 21:02 | Bjoern1982 | Auf diesen Beitrag antworten » | ||||
Teilbarkeitsbeweise 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 |
||||||
20.10.2008, 22:10 | AD | Auf diesen Beitrag antworten » | ||||
Bei (1) werfe ich einfach mal nur in den Ring. |
||||||
21.10.2008, 00:04 | Bjoern1982 | Auf diesen Beitrag antworten » | ||||
Hab schon erstaunlich lang drüber nachgedacht aber ich komm nicht drauf Soll ich zeigen, dass aus n | a²+b² folgt, dass gilt ? Btw Aufgabe (2) konnte ich lösen. |
||||||
21.10.2008, 01:07 | 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 Oder als Spezialfall hier: Arthur Dent wollte vielleicht darauf hinaus, dass du berechnest. Natürlich ohne Garantie, ich kann ja keine Gedanken lesen |
||||||
21.10.2008, 03:35 | 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 Was meinst du hiermit bzw wie sollte mir das helfen ?
Gruß Björn |
||||||
21.10.2008, 04:26 | 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 ? |
||||||
Anzeige | ||||||
|
||||||
21.10.2008, 05:52 | WebFritzi | Auf diesen Beitrag antworten » | ||||
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. 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. |
||||||
21.10.2008, 07:27 | ajax2leet | Auf diesen Beitrag antworten » | ||||
Bist du dir da sicher? So wie ich das sehe, gilt die Gleichung nicht für Exponenten der Form 2k+1 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? |
||||||
21.10.2008, 10:15 | Bjoern1982 | Auf diesen Beitrag antworten » | ||||
@ WebFritzi
Worauf beziehst du dich genau ? Ich kann es beim besten Willen nicht sehen und bei mir wird auch nichts falsch angezeigt oder so Gruß Björn |
||||||
21.10.2008, 15:44 | AD | Auf diesen Beitrag antworten » | ||||
Ganz gewiss nicht - womit dann bewiesen wäre, dass du keine Gedanken lesen kannst. 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. |
||||||
21.10.2008, 16:01 | Bjoern1982 | Auf diesen Beitrag antworten » | ||||
Mit Modulorechnung geht es in der Tat um einiges schneller Kann noch jemand einen Kommentar zu meiner Lösung durch Induktion bzw meiner Lösung zu (3) abgeben ? |
||||||
21.10.2008, 16:17 | AD | Auf diesen Beitrag antworten » | ||||
Diese Logik bleibt mir vollständig verschlossen. 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. |
||||||
21.10.2008, 16:53 | WebFritzi | Auf diesen Beitrag antworten » | ||||
Du liest wohl meine Beitraege nicht ordentlich. Und steht bei dir in meinem letzten Beitrag keine LaTeX-Fehlermeldung "Missing { inserted"? @ajax: Ja, ich bin mir ganz sicher. |
||||||
21.10.2008, 16:53 | ajax2leet | Auf diesen Beitrag antworten » | ||||
Zur Induktion: Zu zeigen Wichtig ist jetzt, dass |
||||||
21.10.2008, 17:01 | Bjoern1982 | Auf diesen Beitrag antworten » | ||||
@ WebFritzi Tut mir leid, jetzt hab auch ichs verstanden wie du das meintest 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 |
||||||
21.10.2008, 17:10 | WebFritzi | Auf diesen Beitrag antworten » | ||||
Die Induktion (ok, der -schritt ) ist ein Einzeiler: Sei (Induktionsvoraussetzung) Dann folgt EDIT: OK, jetzt kann ich ja auch meine "Musterloesung" posten: |
||||||
21.10.2008, 17:15 | ajax2leet | Auf diesen Beitrag antworten » | ||||
Jetzt verstehe ich auch, was du meintest. Ist einfach ein anderer Ansatz |
||||||
21.10.2008, 17:19 | 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. |
||||||
22.10.2008, 01:40 | 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 Auch auf die Gefahr hin mich zu blamieren aber ich hake nochmal nach wegen
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 Gruß Björn |
||||||
22.10.2008, 02:49 | 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. |
||||||
22.10.2008, 20:49 | Bjoern1982 | Auf diesen Beitrag antworten » | ||||
Naja komplett falsch verstanden glaub ich nicht, aber zumindest die falsche Behauptung am Ende benutzt Danke für den Hinweis. So dann bleiben noch die beiden Aufgaben:
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 ? |
||||||
22.10.2008, 21:19 | AD | Auf diesen Beitrag antworten » | ||||
Ja, ist in Ordnung. |
||||||
22.10.2008, 21:30 | Bjoern1982 | Auf diesen Beitrag antworten » | ||||
Dank dir |
|
Verwandte Themen
Die Beliebtesten » |
|
Die Größten » |
|
Die Neuesten » |
|