Kap 3.2
Teilbarkeit

Mit unserem neuen Instrumentarium können wir nun einige Teilbarkeitsregeln herleiten. Dazu gehen wir von der Dezimaldarstellung einer ganzen Zahl a aus:
     a=a_n·10ⁿ+a_n-1·10^n-1 +...+a₁·x+a₀.
Die Quersumme einer Zahl a wird im Folgenden mit QS(a) bezeichnet.

3-er Regel: 10º 1 mod 3 Þ 10ⁿº 1 mod 3 Þ aº a_n+a_n-1+...+a₁+a₀=QS(a) mod 3. Teilt also 3 die Quersumme von a, so teilt 3 auch a - die wohlbekannte Quersummenregel für 3.

9-er Regel: 10º 1 mod 9 Þ .... (siehe oben)

Damit sind wir in der Lage, das dritte der eingangs erwähnten Probleme zu lösen: Wie groß ist QS(QS(QS(4444⁴⁴⁴⁴)))?

AUFGABE 3.13
Berechne ebenso: QS(QS(QS(5555⁵⁵⁵⁵).

11-er Regel: Wegen 10º -1 mod 11 ist 10ⁿº(-1)ⁿ. Damit gilt für a: aº a₀-a₁+a₂-a₃+-...(-1)ⁿ·a_n mod 11. Man nennt diese Art der Quersummenbildung die "alternierende Quersumme" QS_a. So gilt z.B. QS_a(25927)=7-2+9-5+2=11 und wegen zº QS_a(z) damit 11ï 25927. Andererseits gilt QS_a(834439)=1, also 11 teilt nicht 834439.

Regel: 11ïz Û 11ïQS_a(z)

7-er Regel: Es gelten die folgenden Beziehungen: 10⁰º 1 mod 7; 10¹º 3 mod 7; 10²º 2 mod 7; 10³º 6º -1 mod 7; 10⁴º 4º -3 mod 7; 10⁵º 5º -2 mod 7; 10⁶º 1 mod 7 - nun wiederholen sich die Reste. Für a gilt dann aº a₀+3a₁+2a₂-a₃-3a₄-2a₅+a₆+3a₇+2a₈-a₉-3a₁₀.... usw. Wir haben es hier mit einer sogenannten "gewichteten Quersumme" zu tun, die in diesem Fall mit QS₇ bezeichnet werden soll.

Regel: 7ïa Û 7ïQS₇(a)

Für a=87346 gilt: QS₇(a)=6+3× 4+2× 3-7-3× 8=-7, also gilt: 7ï 87346

AUFGABE 3.14
a) Welche Zahlen, die mit nur einer Ziffer geschrieben werden können, sind durch 7 teilbar?
b) Bestimme die kleinste Zahl z, die auf 1997 Einsen endet und durch 7 teilbar ist. Berechne die Quersumme des Quotienten z:7!
c) Bestimme die kleinste fünfstellige Zahl, die auf 1995 endet und durch 7 teilbar ist.

AUFGABE 3.15
Leite eine Quersummenregel für 13 her. (gewichtete Quersumme QS₁₃)

AUFGABE 3.16
a) Es sei a=97.323.565.189.851. Überprüfe a auf Teilbarkeit durch 7, 9, 11, 13.
b) Untersuche z=70.777.475.852.993 auf Teilbarkeit durch 77 und 91.
c) Überprüfe z=33.479.012.345.677.899 auf Teilbarkeit durch 77 und 231.
d) Ist z=19.692.920.748.501 durch 77 (39, 143) teilbar?
e) Ergänze die fehlende Ziffer, so daß die Zahl z durch 7 (9,11,13) teilbar ist: z=45.4_7.479.023.117

Man kann mit diesen neuen Methoden zu jeder beliebigen Zahl geeignete modifizierte Quersummenregeln herleiten, die sich jedoch nicht gut merken lassen und daher von zweifelhaftem Wert sind. Wir geben trotzdem noch eine leicht herzuleitende Regel an:

Wegen 10³º1 mod 37 ergibt sich aus der Dezimalzahldarstellung der Zahl
a=a_na_n-1...a₅a₄a₃a₂a₁a₀=10⁰(a₂a₁a₀)+10³(a₅a₄a₃)+...
die 37-er Regel: Eine Zahl a ist genau dann durch 37 teilbar, wenn die Summe aus den von rechts gebildeten Dreierblöcken durch 37 teilbar ist. Bezeichnet man diese Art der Quersummenbildung mit QS₃₇, so gilt QS₃₇(5946122)=122+946+5=1073=29· 37 - demnach ist 5946122 durch 37 teilbar.

AUFGABE 3.17
a) Überprüfe 545.618.293.733.407 auf Teilbarkeit durch 37.
b)Stelle eine Teilbarkeitsregel für 101 auf.

AUFGABE 3.18
Beweise: Eine Zahl a ist genau dann durch 13 teilbar, wenn die alternierende Summe der von rechts gebildeten Dreierblöcke (a₀+10a₁+100a₂)-(a₃+10a₄+100a₅)+(...)-(...)... durch 13 teilbar ist.

Eine ganz andere Art der Teilbarkeitsüberprüfung eröffnet sich anhand des folgenden Beispiels:
7ïx=10a+b Û7ï y=a-2b (a, bÎN)

mit Zahlen: 6909=10·690+9 Þy₁=690-18=672=10· 67+2 Þy₂=67-4=63 7ï 63, also 7ï6909

Der Beweis der Regel ist einfach in der Kongruenzenschreibweise:
10a+bº0 mod 7 Û bº -10aº4a mod 7 Û 2bº8aºa mod 7 Û a-2bº0 mod 7

AUFGABE 3.19
a) Beweise wie oben: 13ïx=10a+b Û 13ïy=a+4b
b) Beweise allgemeiner: Zu jedem(?) p gibt es ein f(p)ÎZ mit:
pïx=10a+b Û pïx=a-f(p)·b
Wie bestimmt man die Zahl f(p)? Benutze zur Begründung die
Bemerkung zu Satz 3.3.
c) Lege eine Tabelle der f(p) an für 11£p£50.
d) Erweitere den Satz für Zerlegungen der Form: x=10ⁿ·a+b. Stelle auch hier eine Tabelle für n=2,3,4,5 und p=7,13,17,19 her.

AUFGABE 3.20
a) Beweise: 100a+bº0 mod 7 Û a-4bº0 mod 7
b) Ist n nicht durch 3 teilbar, so gilt dies dennoch für z=n¹²-n⁸-n⁴+1.
c) Teilt 7 a³+b³+c³ mit a,b,cÎ N, so teilt 7 mindestens eine der Zahlen a oder b oder c.
d) Es sei a_n:=4n²+1 mit nÎ N. Zeige, daß unendlich viele Folgeglieder durch 13 teilbar sind.
e) Zeige daß unendlich viele Glieder der Folge a_n:=5n²+n+3 durch 17 teilbar sind.
f) Für alle nÎN gilt: 48½5²ⁿ-24n-1

AUFGABE 3.21
Es sei f(n):=n²+n+1 mit nÎN.
a) Für welche nÎN ist f(n) durch 3 teilbar?
b) Zeige, daß f(n) nie durch 9 teilbar ist.
c) Bestimme alle n mit 550<n<560 und 7½f(n).

AUFGABE 3.22
Es sei f(n):=n⁴+n³+n²+n+1 mit nÎN.
a) Bestimme alle nÎN mit 5½f(n).
b) Zeige, daß f(n) nie durch 25 teilbar ist.

AUFGABE 3.23
a) Ist p eine Primzahl größer gleich 3, so ist für keine natürliche Zahl n die Zahl z=(3n-1)p²+1 Primzahl. (Tip: Bilde erst mal einige Beispiele.)
b) Zeige, daß z=1+4·9²ⁿ für alle nÎN durch 5 teilbar ist.
c) Für beliebige natürliche Zahlen u und v gilt: u³+v³º u+v mod 6.
d) Zeige, daß die Summe der Quadrate zweier aufeinander folgender Zahlen nie durch 3 teilbar ist.
e) Suche die kleinste und die größte zehnstellige Primzahl, die aus den Ziffern 0,1,2...,9 besteht.
f) Zeige, daß z=2ⁿ⁺²+3²ⁿ⁺¹ für kein nÎN Primzahl ist. (Tip: Beispiele!)

Download Kap3_1 (19 KB)

Copyright © Michael Dorner, Januar 2001.