Mathematik online lernen im Mathe-Forum. Nachhilfe online

Startseite » Forum » Teilbarkeit bei extrem hohen potenzen

Teilbarkeit bei extrem hohen potenzen

Universität / Fachhochschule

Tags: Potenz, Teilbarkeit

msv-since-1902 aktiv_icon

18:46 Uhr, 06.09.2014

Hallo,
ich komme bei Aufgaben der Teilbarkeit, bei extrem hohen Potenzen nicht klar.
Ich habe hier zwei Aufgaben, bei denen ich nicht weiß, wie ich am besten vorgehen muss.

a)

Zeigen Sie, dass

5^{2014} - 2^{2014}

durch

21

teilbar ist.

b)

Zeigen Sie, dass für allen

n e N

die Zahl

3^{n} - 1

durch 8 teilbar ist.

Vielleicht kann mir jemand dabei helfen ;-)

Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert):
"Ich möchte die Lösung in Zusammenarbeit mit anderen erstellen."

Hierzu passend bei OnlineMathe:
Potenzregeln (Mathematischer Grundbegriff)
Rechnen mit Potenzen

MaStudent aktiv_icon

19:03 Uhr, 06.09.2014

"b) Zeigen Sie, dass für allen neN die Zahl

3^{n} - 1

durch 8 teilbar ist."

Ist das richtig aufgeschrieben?

Man betrachte

n = 1

3^{1} - 1 = 2

Und das ist kaum durch 8 teilbar. Oder heißt es "zeigen oder widerlegen Sie"?

Im Fall a dürften Restklassen bzw. die Modulo-Rechnung helfen.

. .

. Oder?

michaL aktiv_icon

19:21 Uhr, 06.09.2014

Hallo,

wenn du auch nicht die beste Vorgehensweise findest, jede EIGENE ist besser als alle abgeschriebenen.

Ok, zur Aufgabe a):
Es gibt mehrere Herangehensweisen.
Eine funktioniert über modulo unter Verwendung der eulerschen

φ

-Funktion. Wenn du nicht weißt, was das ist, dann hast du entweder die Vorlesung geschwänzt oder musst einen anderen Ansatz wählen.

Ein anderer Ansatz funktioniert über den binomischen Lehrsatz.

Verwende

5^{2014} = 5^{2 \cdot 007} = 2 5^{1007}

und ebenso für

2^{2014}

.

Soweit erstmal, ein bisschen solltest du auch selbst daran Anteil haben.

Mfg Michael

MurksVomOrk aktiv_icon

19:42 Uhr, 06.09.2014

a)

du könntest folgende Rechenregeln brauchen:
1. eine Zahl a ist durch

b

(ohne Rest) teilbar gdw.

a mod b = 0

2. du kannst die Modulo-Berechnung vorziehen:

(a + b) mod c = ((a mod c) + (b mod c)) mod c

3. du kannst den Exponenten in ganzzahlige Faktoren zerlegen und diese dann vorziehen...

x^{y \cdot z} = {(x^{y})}^{z}

4. du kannst die Modulo-Berechnung hier auch früher benutzen

{(x^{y})}^{z} mod c = {(x^{y} mod c)}^{z} mod c = {({(x mod c)}^{y})}^{z} mod c

Spoiler:

a)

stimmt

b)

ist leichter - wie schon erwähnt:

3^{n} - 1 = 0 [mod 8] | =

müsste eigentlich ein Kongruenzzeichen sein

3^{n} = 1 [mod 8] |

hier auch

n = 0 \to 1

ok,

n = 1 \to 3

stimmt nicht, fertig

(n=gerade

\to

stimmt, n=ungerade

\to

stimmt nicht)

b)

stimmt nicht, falls die Formel richtig eingegeben wurde

msv-since-1902 aktiv_icon

13:31 Uhr, 07.09.2014

Bei

b)

sind dabei alle geraden

n

gemeint, das habe ich leider nicht mit aufgeschrieben.

Die modulo rechnung muss man die mit einem taschenrechner machen oder kann man die auch schriftlich machen. Ich habe die noch nie gemacht, weil ich erst im Oktober anfange zu studieren und wir das in der Schule nicht gemacht hatten.

Danke schonmal für die Antworten ;-)

michaL aktiv_icon

14:24 Uhr, 07.09.2014

Hallo,

wenn du modulo nicht kennst, verwende den anderen Tipp.

Mfg Michael

Bummerang

01:25 Uhr, 08.09.2014

Hallo,

betrachten wir mal

(a^{2 \cdot n} - b^{2 \cdot n})

. Dann ist dieser Term durch

(a - b)

teilbar und es gilt:

(a^{2 \cdot n} - b^{2 \cdot n}) = (a - b) \cdot \sum_{k = 0}^{2 \cdot n - 1} (a^{(2 \cdot n - 1) - k} \cdot b^{k})

(a^{2 \cdot n} - b^{2 \cdot n}) = (a - b) \cdot \sum_{k = 0}^{n - 1} (a^{(2 \cdot n - 1) - (2 \cdot k)} \cdot b^{2 \cdot k} + a^{(2 \cdot n - 1) - (2 \cdot k + 1)} \cdot b^{2 \cdot k + 1})

(a^{2 \cdot n} - b^{2 \cdot n}) = (a - b) \cdot \sum_{k = 0}^{n - 1} (a^{(2 \cdot n - 1) - (2 \cdot k)} \cdot b^{2 \cdot k} + a^{(2 \cdot n - 1) - (2 \cdot k) - 1} \cdot b^{2 \cdot k + 1})

(a^{2 \cdot n} - b^{2 \cdot n}) = (a - b) \cdot \sum_{k = 0}^{n - 1} (a \cdot a^{(2 \cdot n - 1) - (2 \cdot k) - 1} \cdot b^{2 \cdot k} + a^{(2 \cdot n - 1) - (2 \cdot k) - 1} \cdot b^{2 \cdot k} \cdot b)

(a^{2 \cdot n} - b^{2 \cdot n}) = (a - b) \cdot \sum_{k = 0}^{n - 1} ((a + b) \cdot a^{(2 \cdot n - 1) - (2 \cdot k) - 1} \cdot b^{2 \cdot k})

(a^{2 \cdot n} - b^{2 \cdot n}) = (a - b) \cdot (a + b) \cdot \sum_{k = 0}^{n - 1} (a^{(2 \cdot n - 2) - (2 \cdot k)} \cdot b^{2 \cdot k})

(a^{2 \cdot n} - b^{2 \cdot n}) = (a - b) \cdot (a + b) \cdot \sum_{k = 0}^{n - 1} (a^{2 \cdot (n - 1) - (2 \cdot k)} \cdot b^{2 \cdot k})

Für

a = 5, b = 2

und

n = 1007

ergibt sich demzufologe:

(5^{2 \cdot 1007} - 2^{2 \cdot 1007}) = (5 - 2) \cdot (5 + 2) \cdot \sum_{k = 0}^{1007 - 1} (5^{2 \cdot (1007 - 1) - (2 \cdot k)} \cdot 2^{2 \cdot k})

(5^{2014} - 2^{2014}) = 3 \cdot 7 \cdot \sum_{k = 0}^{1006} (5^{2 \cdot 1006 - (2 \cdot k)} \cdot 2^{2 \cdot k})

(5^{2014} - 2^{2014}) = 21 \cdot \sum_{k = 0}^{1006} (5^{2012 - (2 \cdot k)} \cdot 2^{2 \cdot k})

Analaog gilt für

a = 3, b = 1

und gerade

n (n

aus der Aufgabenstellung substituiert durch

2 \cdot n'

für gerade

n!) :

(3^{2 \cdot n'} - 1^{2 \cdot n'}) = (3 - 1) \cdot (3 + 1) \cdot \sum_{k = 0}^{n' - 1} (3^{2 \cdot (n' - 1) - (2 \cdot k)} \cdot b^{2 \cdot k})

(3^{n} - 1) = 2 \cdot 4 \cdot \sum_{k = 0}^{\frac{n}{2} - 1} (3^{2 \cdot (\frac{n}{2} - 1) - (2 \cdot k)} \cdot b^{2 \cdot k})

(3^{n} - 1) = 8 \cdot \sum_{k = 0}^{\frac{n}{2} - 1} (3^{2 \cdot (\frac{n}{2} - 1) - (2 \cdot k)} \cdot b^{2 \cdot k})

Man kann im Aufgabenteil

b)

im Falle ungerader

n

die ersten und letzten Paare analog zusammenfassen und den Summanden

(a + b)

(hier

3 + 1 = 4)

ausklammern. Allerdings bleibt dann der mittlere Summand

a^{(\frac{n - 1}{2})} \cdot b^{(\frac{n - 1}{2})}

übrig. Nur wenn dieser Summand ebenfalls durch

(a + b)

teilbar ist, ist auch

(a^{n} - b^{n})

durch

(a + b)

teilbar. In Aufgabe

b)

ergibt sich

3^{(\frac{n - 1}{2})} \cdot 1^{(\frac{n - 1}{2})} = 3^{(\frac{n - 1}{2})} \cdot 1 = 3^{(\frac{n - 1}{2})},

das nur durch 3 und damit nicht durch

3 + 1 = 4

teilbar ist. Deshalb ist

3^{n} - 1

genau dann durch 8 teilbar, wenn

n

gerade ist.

MurksVomOrk aktiv_icon

12:22 Uhr, 08.09.2014

Ist ein wenig "zu genau/viel"? Aber sicher möglich.
schlicht und einfach:

5^{2014} - 2^{2014} = 0 [mod 21]

| Primfaktorzerlegung im Exponenten

5^{2 * n} - 2^{2 * n} = 0 [mod 21]

| Quadrat vorziehen, n = 1007, wollte es nur nicht texen

(5^{2})^{n} - (2^{2})^{n} = 0 [mod 21]

(25)^{n} - (4)^{n} = 0 [mod 21]

| mod 21 vorher berechnen

(25 mod 21)^{n} - (4)^{n} = 0 [mod 21]

(4)^{n} - (4)^{n} = 0 [mod 21]

| gilt für alle n -> statt 2014 kann man jede grade, natürliche Zahl (inkl. 0) nehmen

0 = 0

q.e.d.

Im Normalfall quetscht man das auf Papier in 2-3 Zeilen / eine Doppelzeile, nicht in 7. Aber der OP soll es nachvollziehen können.

b) (Faul-Edition mit "es gilt nur für...")
würde ich einfach umstellen wie oben

f (n) = 3^{n} sei 1 [mod 8] für alle(?) n

und dann

f (n)

rekursiv aufstellen.

f (0) = 1

f (1) = 3 * f (0) = 3 * 1 = 3

f (2) = 3 * f (1) = 3 * 3 = 9 = 1 = f (0) [mod 8]

Daraus folgt zwangsweise, dass es eine Schleife f(0),f(1),f(0),f(1), ... geben muss.
Man kann für gerade n annehmen, dass die zu beweisende Aussage stimmt, und für ungerade eben nicht.

(Faul-Edition nur mit "Nö, stimmt nicht")
Oder noch fauler - wie schon oben von MaStudent angedeutet wurde:

(3^{n} - 1) mod 8 = 0

n=1: 2 = 0 -> nope
(Wobei noch die Frage offen ist, ob die Aufgabe komplett ist.)

Bummerang

12:47 Uhr, 08.09.2014

Hallo MurksVomOrk,

schade, dass Du Dir nicht die Mühe gemacht hast, neben der Aufgsbenstellung auch die weiteren Beiträge zu lesen, denn sonst hättest Du

"Die modulo rechnung muss man die mit einem taschenrechner machen oder kann man die auch schriftlich machen. Ich habe die noch nie gemacht, weil ich erst im Oktober anfange zu studieren und wir das in der Schule nicht gemacht hatten."

gelesen. Dann hättest Du auch gewusst, dass Deine elegante Lösung für den Fragesteller nur MurksVomOrk ist, genauso wie Dein Nickname bereits sagt!

1183615

1183318

	Status: nicht eingeloggt	Noch nicht registriert?