Teilbarkeit für variable Zahlen

31.12.2014, 12:41

Lena95

Teilbarkeit für variable Zahlen

Hey, ich versuche grad ein paar Übungsaufgaben zu machen und hab ziemliche Probleme mit diesen Aufgaben:

Zeigen Sie: Für alle k ∈ N0 gilt
i) $\begin{eqnarray*} 3|2^{2k+1}-2 \end{eqnarray*}$
ii) $\begin{eqnarray*} 5|2^{4k+1}-2 \end{eqnarray*}$
iii) $\begin{eqnarray*} 7|2^{3k+2}-4 \end{eqnarray*}$

Der erste Fall ist noch relativ simpel nachzuvollziehen, da es modulo 3 ja "nur" 3 Restklassen gibt.
2^(2k) modulo 3 hat immer den Rest 1. Wenn man im Exponenten +1 rechnet rechnet man also nochmal *2 und der Rest verdoppelt sich auf 2. Ja diese Zahl -2 ist dann dementsprechend durch 3 teilbar.

Allerdings hab ich keine Idee, wie man sowas beweist. ii) und iii) sind für mich nochmal viel schwieriger. Vllt gibt es da eine grundsätzliche Vorgehensweise oder Ähnliches, wie man da vorgehen kann. Mir fallen Beweise leider immer sehr schwer.

Freue mich über jeden Tip.

Grüße und guten Rutsch ins neue Jahre Wink

31.12.2014, 13:10

ollie3

Auf diesen Beitrag antworten »

RE: Teilbarkeit für variable Zahlen
hallo,
du bist ja schon auf einem guten weg und hast viele sachen richtig erkannt. Freude

Nun zu der frage, wie beweist man das immer gilt 2^(2k)=1 mod 3:
es gibt eine potenzregel, die sagt a^(b*c)=(a^b)^c. Das kann man hierauf
anwenden. Dann überleg mal weiter... Augenzwinkern

gruss ollie3

31.12.2014, 13:50

Lena95

Auf diesen Beitrag antworten »

RE: Teilbarkeit für variable Zahlen

Zitat:

Original von ollie3
hallo,
du bist ja schon auf einem guten weg und hast viele sachen richtig erkannt. Freude

Nun zu der frage, wie beweist man das immer gilt 2^(2k)=1 mod 3:
es gibt eine potenzregel, die sagt a^(b*c)=(a^b)^c. Das kann man hierauf
anwenden. Dann überleg mal weiter... Augenzwinkern

gruss ollie3

Hey, danke für deine Antwort smile

Erstmal muss ich gestehen, dass mich diese Formel etwas verwirrt hat:
2^(2k)=1 mod 3

Rein vom Gefühl hätte ich jetzt gesagt, dass ich zeigen muss das:
2^(2k) mod3 =1, oder ist das das Gleiche?

Wenn ich es richtig verstanden habe, ergibt sich dann aus dem Potenzgesetz:

4^k mod 3 = 1.
Wenn ich jetzt kurz drüber nachdenke, ergibt das natürlich Sinn, dass das für jedes k gilt.
Weil 4^0 mod 3= 1mod3=1. 4^1 mod 3 = 4 mod 3 = 1.
Und wenn ich den Rest beliebig oft mit 4 multipliziere (also 4^k) und modulo 3 rechne, bleibe ich immer in der Restklasse 1.
Ist zwar auf den ersten Blick zu erkennen, fragt sich nur ob das auch bewiesen werden muss, bzw ab wann es als "trivial" einfach stehen lassen kann.

31.12.2014, 14:11

ollie3

Auf diesen Beitrag antworten »

RE: Teilbarkeit für variable Zahlen
hallo,
ja, wenn man modulo-rechnung anwenden darf, ist das schon ein vollständiger
beweis, es gilt also tatsächlich
2^(2k+1)-2=(2^2k)*2 -2=(4^k)*2 - 2=2 -2=0 mod 3, also muss 2^(2k+1)- 2
durch 3 teilbar sein.
Übrigens kann man ii) und iii) ähnlich beweisen Augenzwinkern

gruss ollie3

31.12.2014, 15:00

Lena95

Auf diesen Beitrag antworten »

Hey, danke nochmal smile

Wenn ich jetztmal bei ii) genauso vorgehen würde:

2^(4k+1)-2=16^(k)*2-2=2-2=0 mod 5. Also ist 2^(4k+1)-2 durch 5 teilbar??

Nochmal eine allgemeine Frage:
Wenn eine Zahl x modulo y = 1 ist.
Dann ist x^k modulo y = 1 für jedes k aus den natürlichen Zahlen mit 0?

31.12.2014, 15:13

RavenOnJ

Auf diesen Beitrag antworten »

RE: Teilbarkeit für variable Zahlen
$\begin{align*} 2^{2k}=\left(2^k\right)^2 \end{align*}$ ist eine Quadratzahl und 1 ist der einzige quadratische Rest modulo 3. Daraus folgt $\begin{align*} 2^{2k}-1\equiv 0 \!\!\!\!\mod 3 \end{align*}$ , da immer $\begin{align*} 3\not\mid 2^{n} \end{align*}$

31.12.2014, 15:31

ollie3

Auf diesen Beitrag antworten »

RE: Teilbarkeit für variable Zahlen
hallo,
@lena: ja, ii) hast du jetzt auch richtig gelöst. Freude

Und zu der 2. frage: ja, auch das stimmt, wenn x=1 mod y, dann ist natürlich
auch x^k =1 mod y für alle k el.v. N.
gruss ollie3

Neue Frage »

Antworten »

Teilbarkeit für variable Zahlen

Verwandte Themen