Teilbarkeit durch 13

10.06.2008, 23:15

Zizou66

Teilbarkeit durch 13

Hallo,
ich habe auch ein Rätsel. Es ist nicht so schwer wie die anderen, die hier gepostet werden. Ich hoffe es macht euch trotzdem Spaß.

Wieso ist jede Zahl zwischen 100 und 999, die zweimal hintereinander geschrieben wird, durch 13 teilbar?

Zum Beispiel: 314314, oder 106106. Ich hoffe ihr versteht das Prinzip der Zahlenbauweise, ist irgendwie blöd zu erklären.

10.06.2008, 23:24

kiste

Auf diesen Beitrag antworten »

Naja das ist ja kein wirklich schweres Rätsel Augenzwinkern

Betrachte 1001
Funktioniert übrigens auch mit größeren Zahlen, z.B. sind die 4-stelligen also sowas wie 12341234 immer durch 73 teilbar.

10.06.2008, 23:25

Zizou66

Auf diesen Beitrag antworten »

Ok, dann lest lieber drüber hinweg, wenn es zu einfach ist. Vielleicht mag es ja jemand, der noch nicht so alt, bzw. weit in Mathe ist.

11.06.2008, 20:04

mYthos

Auf diesen Beitrag antworten »

Das gilt nicht nur für Zahlen zwischen 100 und 999, sondern für alle dreiziffrigen Zahlen, wenn die führende Null im zweiten Teil mitgeschrieben wird, z.B. 14014 oder 67067. Und die Teilbarkeit ist nicht nur durch 13, sondern auch durch 11 und 7 gegeben.

mY+

11.06.2008, 23:06

Zizou66

Auf diesen Beitrag antworten »

Sehr cool, das wusste ich auch noch nicht. Freude

Nunja, das Rätsel war auf alle Fälle viel zu einfach....

15.06.2008, 01:15

mYthos

Auf diesen Beitrag antworten »

Hast du mitgekriegt, wie man auf die anderen Primfaktoren kommt?

Hinweis:

1001 = 13 * 11 * 7

Die 1001 sind dir klar?

mY+

15.06.2008, 13:24

Zizou66

Auf diesen Beitrag antworten »

Ich habe das Rätsel irgendwann auch selbst gelöst und habe dabei natürlich auch die 1001 gebraucht, habe auch die Primfaktoren bestimmt, habe mir so direkt allerdings nichts dabei gedacht, dass es da noch andere außer 13 gab.

15.06.2008, 14:37

Arbmosal

Auf diesen Beitrag antworten »

Also mir is nich klar was die 1001 da soll unglücklich

Und wie kann man eigentlich beweisen, dass das für diese zahlen so ist?

MfG
Arbmosal

15.06.2008, 14:50

Zizou66

Auf diesen Beitrag antworten »

Hey, endlich jemand, der mein Rätsel mag smile

Jaa, das ist ja eigentlich genau das Rätsel.

Als Tipp: Induktion

15.06.2008, 19:48

20_Cent

Auf diesen Beitrag antworten »

Was hat denn das Rätsel mit Induktion zu tun?
Dass die Zahl immer durch 1001 teilbar ist, sollte ja klar sein.
mfG 20

15.06.2008, 20:50

Zizou66

Auf diesen Beitrag antworten »

Ehm, weil ich mit Induktion gezeigt habe, dass alle Zahlen dieser Menge durch 13 (bzw. 7,11) teilbar sind.
Man kann das sicherlich auch anders machen...

18.07.2009, 15:40

seraphis

Auf diesen Beitrag antworten »

Wenn man Zahlen der Form (3^n -1) in Primfaktoren zerlegt und irgendwo inner halb der Zerlegung + statt * rechnet (p1 * p2 * p3 + p4 .... * pn), ist das Ergebnis immer durch 3 teilbar, aber ich habe noch kein n gefunden, für welches eine Teilbarkeit durch 13 vorhanden ist. Andere Primfaktoren wie 7 oder 11 sind häufig, die 17 habe ich nur einmal gefunden. Kann jemand das Rätsel um die 13 lösen?
Seraphis

18.07.2009, 16:15

seraphis

Auf diesen Beitrag antworten »

Hier ein Beispiel. Ich setze für n = 10:
(3^10) - 1 = 59048 , Zerlegung : 2 * 2 * 2 * 11 * 11 * 61. Ich setze: 2 * 2 * 2 * 11 + 11 * 61 = 759 = 3 *11 * 23. Hier taucht neben der 3 neu die Primzahl 23 auf, die 2, 7 und 61 verschwinden.
Primfaktoren wie 7 oder 11 sind jeweils in der neuen Zerlegung häufig, die 17 habe ich nur einmal gefunden. Was ist mit der 13 in der neuen Zerlegung. Kann sie jemand für irgendein n finden oder den Gegenbewis liefern?

18.07.2009, 18:01

Auf diesen Beitrag antworten »

Gegenbeispiel
$\begin{eqnarray*} 3^{39}-1 = 2 \cdot 13^2 \cdot 313 \cdot 6553 \cdot 7333 \cdot 797161 \end{eqnarray*}$ ,

und $\begin{eqnarray*} 2 \cdot 13 + 13 \cdot 313 \cdot 6553 \cdot 7333 \cdot 797161 \end{eqnarray*}$ ist offensichtlich durch 13 teilbar. Augenzwinkern

Tatsächlich klappt das aber überhaupt nur, wenn in beiden Teilprodukten Primfaktor 13 enthalten ist, das lässt sich modulo 13 leicht beweisen.

19.07.2009, 00:15

seraphis

Auf diesen Beitrag antworten »

Vielen Dank für das Gegenbeispeil. Bis 3^39 reicht mein Rechner nicht. Kommt der Faktor 13 als neu auftretender Faktor (wie 23 in meinem Beispiel) der neuen Zerlegung schon früher bei kleineren Zahlen vor? Warum klappt die Teilbarkeit mit 3 in allen Beispielen? Lässt sich das beweisen?

19.07.2009, 00:38

Auf diesen Beitrag antworten »

Es ist

$\begin{eqnarray*} 13 \bigm| (3^n-1) \quad \Leftrightarrow \quad 3 \bigm| n \end{eqnarray*}$

und darüber hinaus

$\begin{eqnarray*} 13^2 \bigm| (3^n-1) \quad \Leftrightarrow \quad 39 \bigm| n \end{eqnarray*}$ ,

das lässt sich zeigen, ja.

20.07.2009, 15:57

Reksilat

Auf diesen Beitrag antworten »

Zur Teilbarkeit durch 3:
Sei $\begin{eqnarray*} k=3^n-1 \end{eqnarray*}$ (n>0), dann ist offensichtlich $\begin{eqnarray*} k\equiv 2\; ({\rm mod} 3) \end{eqnarray*}$
Betrachten wir nun die Primfaktorzerlegung $\begin{eqnarray*} k=p_1\cdot...\cdot p_t \end{eqnarray*}$ und bilden, wie von Dir beschrieben, $\begin{eqnarray*} l=p_1\cdot ...\cdot p_{s}+p_{s+1}\cdot ...\cdot p_t \end{eqnarray*}$ .

Jetzt musst Du nur die beiden Summanden modulo 3 betrachten.

Gruß,
Reksilat.

01.08.2009, 16:32

seraphis

Auf diesen Beitrag antworten »

Teilbarbeit
Besten Dank!
Hier noch ein Problem:
Bei der genannten Zerlegung von 3^n -1 treten bei der zweiten Zerlegung (der Summe) bis n = 12 alle Primzahlen bis 107 ausser der 13 (bei n = 39) und der 97 auf. Für welches n ist die Teilbarkeit durch 97 gegeben?
Bei welchem n treten beim Faktorisieren der Werte von 2^n – 1 und 3^n –1 die Primzahlen p auf?

p 2^n -1 3^n -1

2 3 2
3 6 2
5 9 3
7 8 4
11 8 5
13 10 39
17 12 9
19 12 12
23 20 6
29 12 8
31 6
37 12 6
41 5
43 12 12
47 12
53 12
59 12
61 6
67 8
71 8
73 7
79 8
83 12
89 12
97 ?
101 10
103 12 11
107 10

--- Doppelpost zusammengefügt ---

Hier noch ein Problem:
Bei der genannten Zerlegung von 3^n -1 treten bei der zweiten Zerlegung (der Summe) bis n = 12 alle Primzahlen bis 107 ausser der 13 (bei n = 39) und der 97 auf. Für welches n ist die Teilbarkeit durch 97 gegeben

Edit (Dual Space): Diese ständigen Pushposts bringen nichts. Wenn jemand auf deine Frage antworten kann/will wird er es auch so tun.

05.08.2009, 08:38

Auf diesen Beitrag antworten »

Bei aller Wichtigkeit der Analyse des Zahlenmaterials solltest du dich aber auch langsam mal um die Hintergründe bemühen - sonst stellst du dir bei jeder Primzahl $\begin{eqnarray*} p \end{eqnarray*}$ von neuem diese Fragen, das kann dauern... Bei Fragen wie

Zitat:

Original von seraphis
Bei welchem n treten beim Faktorisieren der Werte von 2^n – 1 und 3^n –1 die Primzahlen p auf?

wäre das zuallererst mal der Satz von Euler-Fermat:

$\begin{eqnarray*} a^{\varphi(m)} \equiv 1 \bmod m \end{eqnarray*}$ für alle teilerfremden $\begin{eqnarray*} a,m \end{eqnarray*}$ .

Im Fall $\begin{eqnarray*} m=p \end{eqnarray*}$ mit $\begin{eqnarray*} p>3 \end{eqnarray*}$ sowie $\begin{eqnarray*} a=2 \end{eqnarray*}$ oder $\begin{eqnarray*} a=3 \end{eqnarray*}$ heißt das

$\begin{eqnarray*} a^{p-1} \equiv 1 \bmod p \end{eqnarray*}$

Oder wie oben geschehen bei $\begin{eqnarray*} p=13 \end{eqnarray*}$ bist du vielleicht am Fall $\begin{eqnarray*} m=p^2 \end{eqnarray*}$ interessiert - mit $\begin{eqnarray*} \varphi(p^2) = p(p-1) \end{eqnarray*}$ folgt dann

$\begin{eqnarray*} a^{p(p-1)} \equiv 1 \bmod p^2 \end{eqnarray*}$ .

Ist man nun aber am kleinsten positiven $\begin{eqnarray*} n \end{eqnarray*}$ mit beispielsweise $\begin{eqnarray*} a^n \equiv 1 \bmod m \end{eqnarray*}$ bei teilerfremden $\begin{eqnarray*} a,m \end{eqnarray*}$ interessiert, dann kann man aus Euler-Fermat zumindest folgern:

(1) Es existiert so ein $\begin{eqnarray*} n \end{eqnarray*}$ , und

(2) dieses kleinste $\begin{eqnarray*} n \end{eqnarray*}$ ist ein Teiler von $\begin{eqnarray*} \varphi(m) \end{eqnarray*}$ .

Dieses kleinste $\begin{eqnarray*} n \end{eqnarray*}$ kann sogar direkt $\begin{eqnarray*} n=\varphi(m) \end{eqnarray*}$ sein, i.a. ist es aber ein echter Teiler. Hat man dieses kleinste $\begin{eqnarray*} n \end{eqnarray*}$ gefunden, dann kann man darüber hinaus ähnlich wie hier folgern:

$\begin{eqnarray*} a^{n'} \equiv 1 \bmod m \quad\Leftrightarrow\quad n \bigm| n' \end{eqnarray*}$ .

Beispiel von oben: $\begin{eqnarray*} a=3 \end{eqnarray*}$ und $\begin{eqnarray*} m=13^2 \end{eqnarray*}$ .

Da ist $\begin{eqnarray*} 3^{13\cdot 12} = 3^{156} \equiv 1 \bmod 13^2 \end{eqnarray*}$ , aber es gilt bereits $\begin{eqnarray*} 3^{39} \equiv 1 \bmod 13^2 \end{eqnarray*}$ , wobei $\begin{eqnarray*} 156 = 4\cdot 39 \end{eqnarray*}$ ,

Genaueres erfährst du, wenn du dich tiefer mit der Struktur der primen Restklassengruppe $\begin{eqnarray*} (\mathbb{Z}/m\mathbb{Z})^* \end{eqnarray*}$ auseinandersetzt.

EDIT (12.8.2009): Erst penetrant per PN drängeln, und dann aber Null Reaktion hier im Thread - wirklich feines Verhalten. Finger2

Neue Frage »

Antworten »

Teilbarkeit durch 13

Verwandte Themen