Aussage zur Teilbarkeit beweisen |
25.11.2014, 21:13 | Voldi | Auf diesen Beitrag antworten » | ||
Aussage zur Teilbarkeit beweisen Jede positive ganze Zahl teilt eine Zahl, deren Dezimaldarstellung nur aus Einsen und Nullen besteht. Beispiel: 7 teilt 1001 (Hinweis: Für eine natürliche Zahl n ist die Menge {10^k mod n | k N} endlich.) Heyho, leider habe ich zur Aufgabe oben keine zündende Idee. Hat jemand einen Tipp, wie ich an die Aufgabe rangehen kann? Partitionierung in Klassen vielleicht, aber irgendwie krieg ich es nicht für allgemeine n hin... |
||||
25.11.2014, 21:39 | dastrian | Auf diesen Beitrag antworten » | ||
RE: Aussage zur Teilbarkeit beweisen Partionierung ist eine gute Idee. Schau dir doch für ein gegebenes mal die folgenden Zahlen an: 1, 11, 111, 1111, und so weiter bis 111...111 (aus Einsen bestehend) Und jetzt schau dir die Reste dieser Zahlen bei Division durch an. Entweder, eine der Zahlen hat Rest , dann ist sie durch teilbear, oder ....... ? |
||||
25.11.2014, 21:53 | Voldi | Auf diesen Beitrag antworten » | ||
Oder... sie ist nicht durch n teilbar? Bspw bei 6 ergeben sich die Modulo-Reste 1, 5, 3, 1, 5, 3 ... also teilt 6 keine Zahlen nur aus 1en. Ersetzt man nun eine 1 durch eine 0, verändert sich der Modulo ja um 1, zb 1110 müsste demnach durch 6 teilbar sein. Man muss also nur zeigen, dass jede Zahl mit ihrer "modulo-Reihe" bei 1 beginnt? |
||||
25.11.2014, 22:36 | HAL 9000 | Auf diesen Beitrag antworten » | ||
Richtig. Aber es sind gleiche Reste dabei, z.B. die beiden Einsen - da könnte man doch mal die Differenz der Ausgangszahlen bilden... Allgemein: Sind unter Nichtnull-Resten modulo zwei gleiche Reste dabei? |
||||
25.11.2014, 23:44 | VoldiGast | Auf diesen Beitrag antworten » | ||
Alles klar, Differenzen von Zahlen mit gleichem Ergebnis bei modulo n sind immer durch n teilbar und bestehen nur aus 1en und 0en |
|
Verwandte Themen
Die Beliebtesten » |
Die Größten » |
|
Die Neuesten » |
|