Eine kleine Teilbarkeitsknobelei?

naja, erstmal sollte klar sein, dass es durch 42 teilbar ist, wenn es durch 2 und durch 3 und durch 7 teilbar ist - das macht es wohl schon verdaubarer--oder?

2 ist trivial versuch n gerade oder n ungerade

3 ist auch einfach, weil n^7-n=n(n-1)(n+1)(n^4 - n^2 -1)

7 ist etwas interessanter. Entweder lernt man den Kleinen Fermatschen Satz und wendet ihn auf n(n^6-1) an, oder man rechnet

mit binomischem Satz nach, dass

[(7m+k)^7- (7m+k)] - [k^7 - k] immer durch 7 teilbar ist. Also genuegt es, die Aussage fuer k=-3,-2,-1,0,1,2,3 zu ueberprufen. Wegen des Argumentes fur die 3 sind -1,0,1 sowieso klar und wegen Symmetrie reicht also k=2,3 zu versuchen...viel Spasz

Das Problem ist lösbar mit dreimaliger Verwendung vom kleinen fermatschen Satz:

(Direkt von Wikipedia:

a^p ≡ a (mod p)

wobei a eine ganze Zahl und p eine Primzahl ist.)

Damit haben wir:

n^7 ≡ n (mod 7),

n^3 ≡ n (mod 3),

n^2 ≡ n (mod 2),

für jede beliebige natürliche Zahl, d.h.

7 | (n^7 - n), --- (1)

3 | (n^3 - n), --- (2)

2 | (n^2 - n), --- (3)

Es bleibt hier zu beachten, dass

n^7 - n = (n^3 - n)*(n^4 + n^2 + 1)

und

n^7 - n = (n^2 - n)*(n^5 + n^4 + n^3 + n^2 + n + 1),

sodass (n^3 - n) und (n^2 - n) beide Teiler von (n^7 - n) für jede beliebige natürliche Zahl sind.

Aus (2) und (3) kann man daher herleiten:

3 | (n^7 - n), --- (4)

2 | (n^7 - n), --- (5)

Da 2, 3 und 7 Primzahlen sind (und damit paarweise relativ prim sind, d.h. ggT(2,3) = ggT(2,7) = ggT(3,7) = 1), folgt aus (1), (4) und (5):

(7*3*2) | (n^7 - n),

d.h.

42 | (n^7 -n).

Tja, mein Stichwort wäre das Beweisverfahren mittels vollständiger Induktion. Allerdings habe ich jetzt nicht die Zeit, den entscheidenden Schritt "zu Fuß" durchzuführen.

Anfang:

[Triviale Fälle sind n=0 und n=1; ja, auch die Null kann man schon mal einbeziehen, wird ja im Allgemeinen als natürliche Zahl betrachtet.]

n=2 --> 42 | 126

meinetwegen auch noch n=3 --> 42 | 2184

Voraussetzung:

Die Behauptung sei richtig für n=k.

Dann könnte man die Behauptung in verschiedenen Formen schreiben und müsste sehen, mit welcher der Beweisschritt am Ende am besten ausführbar ist.

42 | (k^7-k)

42 | (k^6-1)k

42 | (k³-1)(k³+1)k

. . .

Behauptung:

42 | [(k+1)^7-(k+1)]

42 | (k+1)[(k+1)³+1][(k+1)³-1]

. . .

Beweis:

Aus der Richtigkeit der Voraussetzung FOLGT LOGISCH die Richtigkeit der Behauptung...

Dabei können sich Fallunterscheidungen notwendig machen, etwa, wenn k gerade bzw. ungerade ist...

42 = 7 * 3 * 2 ist ein eindeutige Primzahlzerlegung für 42. Das ist wichtig. 42 ist eine sphenische Zahl, die zweite sphenische Zahl.

n^7-n = n * (n^6-1) ist abwechselnd das Produkt eines geraden n mit einem ungeradem n^6-1 oder eines ungeraden n und eines geraden n^6-1. Damit ist gewährleistet, das 2 immer ein Teiler des Produktes ist. Gleichzeitig ist immer eine ungerade Zahl ebenfalls intuitiv Teiler. Dabei kommt es immer so vor, das wenn n durch 3 teilbar ist, n^6-1 durch sieben teilbar ist, und wenn n durch 7 teilbar ist n^6-1 durch 3 teilbar ist.

Dies lässt sich zeigen, in dem man n=2^x*3^y*7^z*weitere Primzahlenpotenzen einsetzt. {x,y,z} auf N^3. Die Reihe beginnt mit 2^7-2=126=2*3*3*7. n=4 16380=2*2*3*3*5*7*13

3^7-3=2184=2*2*3*3*5*7*13;n=578120=2*2*2*3*3*5*7*31

n n(n^6-1)=n*(n^3-1)(n^3+1)

2 2 7 9

3 3 26 28

4 4 63 65

5 5 124 126

6 6 215 217

7 7 342 344

8 8 511 513

9 9 728 730

10 10 999 1001

11 11 1330 1332

Bietet Fallunterscheidungen.

=> Zahlkörpersieb.

Einen schönen Sonntagmorgen zusammen!

Ich dachte das Problem wäre längst gelöst. Also, dann will ich auch noch eine Kleinigkeit beitragen.

n^7 – n = n(n^6 –1) = n(n³-1)(n³+1)

= n (n-1) (n²+n+1) (n³ - (-1)³)

= n (n-1) (n²+n+1) (n+1) (n²-n+1)

=(n-1) n (n+1) (n²-n+1) (n²+n+1)

Da die ersten 3 Faktoren aufeinanderfolgende natürliche Zahlen sind, ist Teilbarkeit durch 2 und 3 gewährleistet.

Setze nun n=7k+m mit 0<=m<=6 ein (eine solche Darstellung existiert für jedes n),

dann folgt Teilbarkeit durch 7 für m=1, m=0 und m=6 mittels der ersten 3 Faktoren.

Die beiden letzten Faktoren ergeben:

((7k+m)²-7k-m+1) ((7k+m)²+7k+m+1)

=(7a+m²-m+1) (7b+m²+m+1) (für ganze Zahlen a und b)

Für m=3 und m=5 ist der 1.Faktor Vielfaches von 7

Für m=2 und m=4 ist der 2.Faktor Vielfaches von 7

Somit ist für jedes n Teilbarkeit durch 7 bewiesen.

Insgesamt ist n^7 – n also durch 2*3*7=42 teilbar.

Nein, das geht nicht!

..