Hallo zusammen,
ich habe durch Zufall festgestellt, daß die Formel (7hochX)+2 immer Ergebnisse liefert, die durch 3 teilbar sind, wenn X=0 oder größer ist, wobei das dann aber nur für die natürlichen Zahlen wie 1,2,3… usw. gilt. Warum ist das so?
Danke für Antworten!
Rüdiger
Hallo,
3 teilt 7 mit Rest 1, also 7 mod 3=1. Nun gilt 7n+1 mod 3=(7n mod 3)*(7 mod 3) mod 3, also unter der Annahme das 7n mod 3=1, folgt 7n+1 mod 3=1. Ergo 7x mod 3=1 gilt für jedes natürliche x größer 0. Wenn Du die zwei noch dazuaddierst folgt Deine Behauptung.
Gruss
Enno
Hallo Rüdiger,
ich habe durch Zufall festgestellt, daß die Formel (7hochX)+2
immer Ergebnisse liefert, die durch 3 teilbar sind, wenn X=0
oder größer ist, wobei das dann aber nur für die natürlichen
Zahlen wie 1,2,3… usw. gilt. Warum ist das so?
wie wärs mit einem Beweis durch vollständige Induktion nach x:
Behauptung: Für jede natürliche Zahl x oder x=0 gilt 7^x+2 ist ohne Rest
durch 3 teilbar (7^x+2=3y 7^x=3y-2 für eine natürliche Zahl y).
Induktionsanfang: Für x=0 gilt 7^0+2=3=3*1. Die Behauptung stimmt also für x=0.
Induktionsvoraussetzung: Gelte die Behauptung für eine natürliche Zahl x oder
x=0.
Induktionsschluß: Es gilt 7^(x+1)=7^x *7= (nach Voraussetzung) (3y-2)*7
=3*(7y)-14=3*(7y)-3*4-2=3*(7y-4)-2. Also läßt sich auch 7^(x+1) in der
gewünschten Form darstellen: 7^(x+1)=3*y’-2 mit y’ natürliche Zahl.
Damit ist die Behauptung für x+1 anstelle von x gezeigt und es folgt die
Behauptung mit dem Prinzip der vollständigen Induktion.
Hoffe das ist einigermaßen verständlich, falls nicht frag nach 
Viele Grüße
Sebastian
Hallo,
ich sehe gerade, daß Du die Aussage auch für x=0 beweisen willst. In dem Fall beginnt man mit 70 mod 3=1 mod 3=1.
Gruss
Enno
Hallo Rüdiger,
deine Entdeckung lässt sich sogar noch verallgemeinern. Wenn b und t zwei natürliche Zahlen sind, für die
b mod t = 1
gilt (d.h. bei Division von b durch t bleibt der Rest 1), so gilt für alle nichtnegativen ganzen Zahlen:
b^x+(t-1) mod t = 0
(d.h. b^x+(t-1) ist durch t teilbar).
Beweisen lässt sich dies z.B. mittels volständiger Induktion (völlig analog wie in Sebastians Antwort).
Viele Grüße
Jens
Hallo,
ein anderer aus der Zahlentheorie bekannter Zusammenhang (nach Euler) ist es, wenn man zwei teilerfremde Zahlen a,b (also ggT(a,b)=1) nimmt, ist
aphi(b)-1 resp. aphi(b)+b-1
immer durch b teilbar. Und damit natürlich auch
akphi(b)-1 resp. akphi(b)+b-1
für jedes natürliche k>=1. Dabei ist phi(b) die Anzahl der teilerfremden Zahlen von b von 1 bis b-1. Im Bsp. a=7 und b=3, also phi(3)=2, würde man somit 49k-1 mod 3=0 für k>=1 erhalten.
Gruss
Enno
Nachtrag
Hallo,
am Bsp. sieht man, daß phi(b) nicht unbedingt der kleinste Exponent mit
an-1 mod b=0
ist. Zusätzlich in Frage kommen aber nur echte Teiler von phi(b), im Bsp. gerade die 1, also 7-1 mod 3=0 und damit wieder 7k-1 mod 3=0. Betrachtet man z.B. a=7 und b=5, also phi(b)=4, wäre also zu überprüfen, ob
71-1 mod 5=0 (nicht der Fall)
72-1 mod 5=0 (ebenfalls nicht der Fall)
Damit verbleibt wirklich nur die 4 als kleinster Exponent (größer der 0) mit 74-1 mod 5=0.
Gruss
Enno
Hallo,
danke für die Antwort, aber das mit der Modulo-Funktion habe ich noch nie kappiert.
Rüdiger
[Team: Nachname entfernt]
Hallo,
a mod n für zwei natürliche Zahlen (mit n>0) ist einfach der Rest, der beim teilen von a durch n ensteht, also z.B. 23 mod 7=2 (da 23=3*7+ 2 ), 12 mod 3=0 (da 12=4*3+ 0 ) und 7 mod 3=1 (da 7=2*3+ 1 ). Ist a div n die ganzzahlige Division durch n (in den Bsp. 3,4 und 2), so gilt a=(a div n)*n + (a mod n) bzw. a mod n=a-(a div n)*n. Man kann a mod n auch durch sukzessives Abziehen gewinnen:
a mod n=a falls a=n
Die wichtigsten Gesetzmäßgkeiten beim rechnen „mod n“ sind eigentlich:
(a+b) mod n = ((a mod n) + (b mod n)) mod n
(a*b) mod n = ((a mod n) * (b mod n)) mod n
d.h. das Modulo kann noch „nach innen“ gezogen werden. Die Beziehungen macht man sich leicht klar, wenn a=kn+r, b=ln+s mit 0