Autor |
Beitrag |
Sven
| Veröffentlicht am Freitag, den 30. März, 2001 - 14:26: |
|
Hi Leute! Was ich immer schon mal wissen wollte: Gibt es für die Teilbarkeit einer Zahl durch ein beliebiges n (prim) eigentlich eine Art Algorithmus? Beispiel: Durch 2 ist eine Zahl teilbar, wenn die letzte Stelle gerade ist Durch 3 ist eine Zahl teilbar, wenn ihre Quersumme durch 3 teilbar ist Durch 11 ist eine Zahl teilbar, wenn ihre alternierende Quersumme durch 11 teilbar ist Kann man jetzt, ohne daß dieses n durch (2,3,5,7,11) teilbar ist, sagen, wie diese Zahl auszusehen hat? |
doerrby
| Veröffentlicht am Freitag, den 30. März, 2001 - 15:24: |
|
Es gibt eine allgemeine Teilbarkeitsregel, bei der aber die meisten Fälle unpraktikabel sind. Die Anwendung geht folgendermaßen: Man sucht sich ein günstiges Vielfaches k*n vom Teiler n, d.h. da wir im Dezimalsystem rechnen eine Zahl in der Nähe einer Zehnerpotenz (je näher, desto besser). Diese zerlegen wir so: k*n = 10m + s Will man nun eine Zahl x auf Teibarkeit durch n prüfen, so zerlegt man diese Zahl von hinten in Päckchen zu je m Ziffern und multipliziert jedes Päckchen mit einer Potenz von (-s), das erste mit (-s)0, das zweite mit (-s)1 usw. Dann zählt man diese multiplizierten Päckchen alle zusammen und diese neue (wesentlich kleinere) Summe lässt nach Teilung durch n den gleichen Rest wie x, d.h. speziell: Wenn diese Summe durch n teilbar ist, dann ist auch x durch n teilbar. Beispiel: n=17 , x=147815 Vielfaches: 6*17 = 102 = 102 + 2 Also zerlege ich 147815 in Zweierpäckchen und multipliziere mit (-20)=1 , (-21)=-2 und (-22)=4 . Anschließend addiere ich: 15 * 1 + 78 * (-2) + 14 * 4 = -85 = -5 * 17 Also ist 147815 durch 17 teilbar. Wendet man diese Regel auf Zahlen an, die nur aus Potenzen von 2 und 5 bestehen (2,4,5,8,10,...), ist immer nur das erste Päckchen interessant, da die weiteren durch die Multiplikation zu 0 werden. Für die Zahl 11 gibt es übrigens nach diesem System noch zwei weitere Regeln: 11 = 10 + 1 (Deine Regel: alternierende Quersumme) 9*11 = 100 - 1 (von hinten in Zweierpäckchen und dann zusammenzählen) 91*11 = 1000 + 1 (von hinten in Dreierpäckchen, dann alternierende Summe) Bei den meisten Zahlen ergibt sich aber leider keine praktikable Regel aus dieser allgemeinen Regel. Falls Du einen Beweis führen willst: Man kann es recht einfach mit Kongruenzen (modulo) beweisen. Gruß Dörrby |
|