| 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 |
|
