witzeforum.de

Beweise oder widerlege!

Eine Zahl ist durch 2^n teilbar, wenn die letzten n Ziffern durch 2^n teilbar sind.

Eine Zahl ist durch 3^n teilbar, wenn die Quersumme der Zahl durch 3^n teilbar ist.

Viel Spaß!

zu erstens:

es reicht zu zeigen, das 2^n 10^n teilt.

2^n teilt 10^n <=> Ex. x aus N mit x = 10^n / 2^n = 5^n

5^n ist aus N, qed.

zu zweitens:

gegenbeispiel:

9981 hat Quersumme 27,
9981 / 27 = 369,67

Es gilt nur 3|(10-1); 9|(100-1) und 27|(1000-1); 81 teilt aber nicht mehr 9999.
für 27 ergibt sich somit folgende Teilbarkeitsregel:
Sei a=Summe ai*10^i
dann folgt:
a mod 27=(Summe ai*10^i) mod 27
=Summe (ai*10^i mod 27)
=Summe (ai*(10^i mod 27))
mit 10 mod 27=10; 100 mod 27=19 und 1000 mod 27=1 folgt:
=Summe (a(i*3)*(1)+a(i*3+1)*(10)+a(i*3+2)*(19))
also eine gewichtete Quersumme mit Abwechselnd Gewichten 1,10,19 (oder -8; was einfacher ist) muss durch 27 teilbar sein.

Analog 81
mit Gewichten 1, 10, 19; 28; 37; 46; 55; 64; 73;
(der Zyklus ist Länger, da 81 Teiler von 10^9-1 ist.)

bei 3^5 ist der Zyklus 27 lang und generell
ist bei 3^n der Zyklus 3^(n-2) lang. (das ist Gleichbedeutend mit 3^n|10^(3^(n-2)) -1)

Beweis:
Induktion
Anfang bei 2: 9|9

Schritt: Es gelte: 3^n|10^(3^(n-2)) -1)
=>
3^(n+1)|10^(3^(n-2)) -1)*3
da 10^(3^(n-2))-1 )+10^(3^(n-2)) *2-1)+10^(3^(n-2)) *3-1) durch 3 teilbar und
(10^(3^(n-2))-1 )+10^(3^(n-2)) *2-1)+10^(3^(n-2)) *3-1))*10^(3^(n-2)) -1)=10^(3^(n-1)) -1)
gilt:
3^(n+1)|10^(3^(n-1)) -1)
damit gilt die Behauptung für alle n>1.

hört sich alles ganz gut an, aber jetzt was für profis:

Eine Zahl ist durch 7 teilbar, wenn folgendes geht:

Beispiel 441.

Nehmt die letzte Zahl weg:
44
Verdreifacht das Ergebnis:
132
Zählt die letzte Zahl dazu:
133
Macht das ganze nochmal:
13
39
42
Und nochmal:
4
12
14
Und nochmal:
1
3
7

Kommt eine 7 heraus, ist die Zahl durch 7 teilbar,
wenn nicht, dann nicht

Beweis!

Beweis:
Verfahren lautet: mache aus 10a+b eine 3a+b
in Restklassen mod 7 ist das offensichtlich. (da 7a stets durch 7 Teilbar)

du betrachtest jetzt aber nur zweistellige Zahlen.

Und was genau soll es dir bringen, 10a in 3a umzuwandeln?

Ich hab nie gesagt, dass a einstellig sei. 10a durch 3a zu ersetzen bringt, dass es kleiner wird.

Noch mal Langsam:
Sei n eine natürliche Zahl.
Dann lässt sie sich darstellen als a*10+b
Dann macht dein Verfahren:
0. a*10+b
1. a (letzte Ziffer abschneiden)
2.a*3 (mal 3)
3.a*3+b (letzte Ziffer wieder anhängen)

Trick ist
1. a*3+b ist kleiner als n=a*10+b
2. beide lassen bei Division durch 7 den gleichen Rest. (Sie unterscheiden sich ja um 7*a)

Führt man das Verfahren weiter lässt die entstehende Zahl immer den selben Rest bei Division durch 7, und wird kleiner.

Das Verfahren bricht ab, wenn die Zahl einstellig, also <10 wird.
Kommt eine 7 raus, ist es damit durch 7 teilbar, sonst nicht.

------------------------------------------------------------------------------

Hier mal ne Allgemeine Teilbarkeitsregel:
Man möchte prüfen, ob n durch a=m*2^x*5^y teilbar ist. Dabei sei m weder durch 2 noch 5 teilbar.
Schritt 1
2^x:
Man prüfe, ob die letzten x Stellen von n durch 2^x teilbar sind.
Wenn ja: n ist durch 2^x teilbar.
Schritt 2
5^y:
Man prüfe, ob die letzten y Stellen von n durch 5^y teilbar sind.
Wenn ja: n ist durch 5^y teilbar.
Schritt 3:
m:
man schneide n in Stücken der Länge (m-1) und addiere diese Stücke auf.
Wenn diese Zahl durch m Teilbar ist, so ist die Zahl n durch m teilbar.

Besteht n alle 3 Tests, ist sie durch a teilbar.

Anmerkung: Schritt 3 lässt sich manchmal vereinfachen zu:
man Suche das minimale z mit m ist Teiler von 10^z-1
dann modifiziere man Schritt 3, indem man in Stücke der Länge z-1 schneidet (statt der Länge m-1)

Beispiel 13: 999999 ist durch 13 teilbar, also reicht es in Stücke der Länge 6 zu schneiden (Statt 12)

Weitere Vereinfachung zu 3.
ist m ein Teiler von 10^(z/2)+1 (z muss natürlich gerade sein)
dann kann man die n in Stücke der Länge z/2 zerlegen und bildet dann eine alternierende Summe alse ersten Block addieren, 2. subtrahieren 3. addieren 4. subtrahieren...

Wieder Beispiel 13:
13 teilt 1001 also anwendbar
oder 137 teilt 10001 also teilt man die Zahlen in Blöcke der Länge 4.

ah okay, erklärung ist jetzt viel klarer geworden.

Dann beweis doch mal:

Eine Zahl ist durch 11 teilbar, wenn ihre alternierende Quersumme
(x1-x2+x3-x4...) durch 11 teilbar oder 0 ist.

Feststellung: 11 ist Teiler von 99, 11 ist Teiler von 11 also 2-fach-verbesserte Regel3.

Zum Beweis:
Sei n=a0*10^0+a1*10^1+a2*10^2...
dann ist
n mod 11=(a0*10^0+a1*10^1+a2*10^2...) mod 11
=(a0*10^0 mod 11)+(a1*10^1 mod 11)+(a2*10^2 mod 11)+...
=a0*(10^0 mod 11)+a1*(10^1 mod 11)+a2*(10^2 mod 11)+...
=a0*(+1)+a1*(-1)+a2*(+1)+....
das ist die alternierende Quersumme.
fertig.


um vieleicht nochmal das Verfahren generell zu erklären (für teilbarkeit durch a:
man sollte zunächst folgendes wissen:
(n1+n2)/a=(n1/a)+(n2/a) (folgt aus Distributivgesetz; Ermöglicht in einer Summe die Summanden einzeln zu teilen.)
=>(n1+n2)mod a=(n1 mod a)+(n2 mod a)
[mod ist der Rest bei Division durch; hier gilt Gleichheit im Restklassenring mod a; d.h. auf beiden Seiten lässt die Zahl den gleichen Rest bei Division durch a; wenn a z.B. 7 ist, dann ist nach der Auffasung 2=9, da 2 und 9 bei der Division durch 7 beide den Rest 2 lassen.]
(n1*n2)/a=(n1/a)*n2 [folgt aus assoziativgesetz]
damit:
(n1*n2) mod a=(n1 mod a)*n2
und
(n^x)/(a^x)=(n/a)^x [folgt aus assoziativgesetz,Kommutativ und Potenzgesetzen]
=>(n^x) mod (a^x)=(n mod a)^x
Mit diesen Werkzeugen machen wir uns dran die Zahl n so klein wie möglich zu machen.


Zerlege a in 2-en, 5-en und Rest. [a=m*2^x*5^y]
nach 2-en und 5-en Reicht es sich die letzten x bzw. y Stellen von
[Beweis: n=n1*10^x+n2;
n mod (2^x)=(n1*10^x+n2) mod (2^x)
=n1*(10^x mod 2^x)+n2 mod (2^x)
=n1*(10 mod 2)^x+n2 mod (2^x)
=n1*(0)^x+n2 mod (2^x)
=0+n2 mod (2^x)
=n2 mod (2^x)
also der Rest der x letzten Ziffern. Analog mit 5^y]

Nun zu m
man betrachte 10^i mod m
nun suche man minimales i mit 10^i mod m=+oder -1
Fall -1 (wie bei 11):
man Schreibe n als:
n mod m=(a0*10^(i*0)+a1*10^(i*1)+a2*10^(i*2)...) mod m
=(a0*10^(i*0) mod m)+(a1*10^(i*1) mod m)+(a2*10^(i*2) mod m)+...
=a0*(10^(i*0) mod m)+a1*(10^(i*1) mod m)+a2*(10^(i*2) mod m)+...
=a0*(+1)+a1*(-1)+a2*(+1)+....
Das ist die Alternierende "Quersumme" mit Blocklänge i

analog
Fall 1 (wie bei 3, 9)
man Schreibe n als:
n mod m=(a0*10^(i*0)+a1*10^(i*1)+a2*10^(i*2)...) mod m
=(a0*10^(i*0) mod m)+(a1*10^(i*1) mod m)+(a2*10^(i*2) mod m)+...
=a0*(10^(i*0) mod m)+a1*(10^(i*1) mod m)+a2*(10^(i*2) mod m)+...
=a0*(+1)+a1*(+1)+a2*(+1)+....
Das ist die "Quersumme" mit Blocklänge i

[man kann natürlich auch alle "einfachen" Potenzen suchen, dann muss man sich aber mehr Reste merken, bekommt aber kleinere Blöcke]

Beweis der Exitenz von einem solchen i (also 10^i mod m=1):
Die 10^i mod m können nicht 0 sein, da sonst m durch 2 oder 5 teilbar wäre (wegen eindeutiger Primfaktorzerlegung von 10^i=2^i*5^i und m)
damit kann 10^i maximal (m-1) Werte annehmen.
Es existiert ein j<k<(m) mit
10^j mod m=10^k mod m (Schubfachschluss: bis spätestens m muss ein Wert doppelt auftreten)
dann gilt aber für alle g>0:
10^(j+g) mod m=10^(k+g) mod m
=>
10^(k-j) mod m=1
damit ist so ein i gefunden.

(Die komplette theoritische Untermauerung gibt's im 1. Studienjahr beim Mathestudium Stichwort: Algebra, Gruppen, Ringe, Körper, wenn man dass erstmal gehört hat, geht der Beweis so: Das ist ja ein Restklassenring, damit ist alles offensichtlich.)

Übungsbeispiel:
Welchen Rest lässt
12345678987654321 bei Division durch 13:

Man weiß: 7*11*13=1001
also Blöcke der länge 3; alternierende Summe:
12345678987654321 mod 13=
-12+345-678+987-654+321 mod 13=
309 mod 13=(260+49) mod 13=49 mod 13=10
war ganz einfach.

selbes bei Division durch 137
erst mal i suchen

10^1 mod 137=10
10^2 mod 137=100
10^3 mod 137=1000 mod 137=1000-5*137=41
10^4 mod 137=10^3 mod 137*10=410 mod 137=-1

Also alternierende Summe Länge 4

12345678987654321 mod 137=
1-2345+6789-8765+4321 mod 137=1+(4444)-(4444) mod 137
=1
Also Rest 1

jo sieht gut aus

Auch wenn ich nur bis zur hälfte gelesen habe.

danach kammen doch erst die spannenden stellen.

888xuerong-4:
Cheap Uggs UK