Endziffern und Reste < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | a) Mit welcher Ziffer endet die Zahl [mm] 3^{80}
[/mm]
b) Welchen Rest lässt [mm] 2^{81} [/mm] bei Division durch 5? |
Hi,
bei der a) habe ich so angefangen.
[mm] 3^2=9
[/mm]
[mm] 81=3^23^2=3^{2+2}=3^4
[/mm]
Mit dem Satz von Euler folgt nun
[mm] 81=3^4\equiv [/mm] 1 (mod 10)
Jetzt kennen wir die Regel [mm] a\equiv [/mm] b (mod m) => [mm] a^n \equiv b^n [/mm] (mod m)
Damit erhalten wir dann
[mm] 81^{20}=(3^4)^{20}=3^{80} \equiv 1^{20} [/mm] (mod 10)
so, aber woran erkenne ich jetzt die letzte Ziffer???? Das verstehe ich gerade nicht.... kann mir das vielleicht jemand erklären??
Grüße
|
|
| |
|
Hallo steve.joke,
> a) Mit welcher Ziffer endet die Zahl [mm]3^{80}[/mm]
>
> b) Welchen Rest lässt [mm]2^{81}[/mm] bei Division durch 5?
> Hi,
>
> bei der a) habe ich so angefangen.
>
> [mm]3^2=9[/mm]
>
> [mm]81=3^23^2=3^{2+2}=3^4[/mm]
>
> Mit dem Satz von Euler folgt nun
>
> [mm]81=3^4\equiv[/mm] 1 (mod 10) ![[ok]](/images/smileys/ok.gif "[ok]")
>
> Jetzt kennen wir die Regel [mm]a\equiv[/mm] b (mod m) => [mm]a^n \equiv b^n[/mm]
> (mod m)
Ja!
>
> Damit erhalten wir dann
>
> [mm]81^{20}=(3^4)^{20}=3^{80} \equiv 1^{20}[/mm] (mod 10)
Nun [mm]1^{20}=1[/mm], also [mm]3^{80}\equiv 1 \ (\operatorname{mod}10)[/mm]
Also hat die Kongruenz [mm]3^{80}\equiv x \ (\operatorname{mod}10)[/mm] die Lösung [mm]x=1[/mm]
Es lässt also [mm]3^{80}[/mm] bei Division durch 10 den Rest 1, dh. die Einerziffer ist 1 (die Einerziffer ist ja gerade der Rest bei Division durch 10)
>
>
> so, aber woran erkenne ich jetzt die letzte Ziffer???? Das
> verstehe ich gerade nicht.... kann mir das vielleicht
> jemand erklären??
>
>
> Grüße
LG
schachuzipus
>
|
|
|
| |
|
HI
> Damit erhalten wir dann
>
> $ [mm] 81^{20}=(3^4)^{20}=3^{80} \equiv 1^{20} [/mm] $ (mod 10)
> Nun $ [mm] 1^{20}=1 [/mm] $, also $ [mm] 3^{80}\equiv [/mm] 1 \ [mm] (\operatorname{mod}10) [/mm] $
> Also hat die Kongruenz $ [mm] 3^{80}\equiv [/mm] x \ [mm] (\operatorname{mod}10) [/mm] $ die Lösung x=1
> Es lässt also $ [mm] 3^{80} [/mm] $ bei Division durch 10 den Rest 1, dh. die Einerziffer ist 1 (die Einerziffer ist ja gerade der Rest bei Division durch 10)
D.h. meine Endziffer ist die 1?? Und was hat das ganze dann mit [mm] 81^{20} [/mm] zu tun? Heißt das, dass diese Zahl gar nicht wichtig ist??
Und in welchem Fall wäre dann z.B. die 1 nicht Endziffer?? Denn den Satz von Euler müsste ich ja immer anwenden könne, oder nicht??
|
|
|
| |
|
| Status: |
(Antwort) noch nicht fertig  | | Datum: | 14:46 Di 24.05.2011 | | Autor: | Eliss |
Hallo steve.joke,
> > Damit erhalten wir dann
> >
> > [mm]81^{20}=(3^4)^{20}=3^{80} \equiv 1^{20}[/mm] (mod 10)
>
> > Nun [mm]1^{20}=1 [/mm], also [mm]3^{80}\equiv 1 \ (\operatorname{mod}10)[/mm]
>
> > Also hat die Kongruenz [mm]3^{80}\equiv x \ (\operatorname{mod}10)[/mm]
> die Lösung x=1
>
> > Es lässt also [mm]3^{80}[/mm] bei Division durch 10 den Rest 1, dh.
> die Einerziffer ist 1 (die Einerziffer ist ja gerade der
> Rest bei Division durch 10)
>
>
> D.h. meine Endziffer ist die 1?? Und was hat das ganze dann
> mit [mm]81^{20}[/mm] zu tun? Heißt das, dass diese Zahl gar nicht
> wichtig ist??
Ja 1 ist deine gewünschte Endziffer.
Wie du richtig festgestellt hast in deinem Beweis ist
[mm] 81^{20}=(3^4)^{20}=3^{80}.
[/mm]
Also ist deine [mm] 81^{20} [/mm] lediglich eine andere (durch Umformen mit Potenzgesetzten erreichte) Darstellung von eben [mm] 3^{80}.
[/mm]
> Und in welchem Fall wäre dann z.B. die 1 nicht Endziffer??
Zum Beispiel bei [mm] 3^{81}. [/mm]
Da wäre die Endziffer 3, das ist schließlich
[mm] 3^{80}*3 [/mm] (mod 10)
Und der Rest mod 10 ist die Einerziffer, also die Endziffer.
Um das zu erhalten musst du auch hier geschickt argumentieren (so wie bei deiner Aufgabe).
Hoffe, das hilft dir weiter!
Lg, Eliss
|
|
|
| |
|
Hi nochmal.
D.h., wenn nach der Endziffer gefragt ist, sollte man immer mit dem mod 10 arbeiten, richtig?? Weil ja nur dann die Zahl vor dem Mod die Endziffer angibt, richtig oder???
Was ist aber, wenn ich z.B. sowas hätte [mm] 3\equiv [/mm] 5 (mod 9)
das sind jetzt ausgedachte zahlen und wahrscheinlich hauts auch gar nicht hin, aber wie könnte man hier dann die Endziffer bestimmen??
Und könnt ihr mir vielleicht noch Tipps zur b) geben??
Grüße
|
|
|
| |
|
Hallo steve.joke,
> Hi nochmal.
>
> D.h., wenn nach der Endziffer gefragt ist, sollte man immer
> mit dem mod 10 arbeiten, richtig?? Weil ja nur dann die
> Zahl vor dem Mod die Endziffer angibt, richtig oder???
Ja.
>
> Was ist aber, wenn ich z.B. sowas hätte [mm]3\equiv[/mm] 5 (mod 9)
Sicher meinstest Du
[mm]3^{k} \equiv 3 \ \operatorname{mod} \ 9[/mm]
Diese ist unlösbar, da 3 und 9 nicht teierfremd sind.
>
> das sind jetzt ausgedachte zahlen und wahrscheinlich hauts
> auch gar nicht hin, aber wie könnte man hier dann die
> Endziffer bestimmen??
>
>
> Und könnt ihr mir vielleicht noch Tipps zur b) geben??
Bei Teilaufgabe b) wird genauso wie bei Teilaufgabe a) vorgegangen.
>
> Grüße
Gruss
MathePower
|
|
|
| |
|
Also um die b) zu verstehen, habe ich mir mal ein bsp. im internet angeschaut.
http://www.physik-schule.de/download/pdf/Primzahl/Resteberechnung.pdf
Hier berechnen die den Rest von [mm] 2^{1000} [/mm] bei der Div durch 3.
Die gehen dabei wie folgt vor:
[mm] 2\equiv [/mm] 2 mod 3
Hier schon mal meine erste Frage, wie kommen die auf diese Zeile?? Ok, die erste 2 kommt von [mm] 2^{1000} [/mm] und durch 3 wird geteilt, aber wie kommen die dann auf die zweit 2 hinter dem [mm] \equiv [/mm] ??
[mm] 2\equiv [/mm] 2 mod 3
[mm] 2^2=4=3*1+1 \equiv [/mm] 1 mod 3
Hier genauso, wie kommen die von 3*1+1 auf [mm] \equiv [/mm] 1 mod 3???
[mm] 2^3\equiv [/mm] 2 mod 3
[mm] 2^4\equiv 4\equiv [/mm] 1 mod 3
wieso ist hier auf einmal [mm] 2^4\equiv [/mm] 4??
und daraus folgt dann [mm] 2^{1000}\equiv [/mm] 1 mod 3, also ist der Rest 1.
Hoffe, ihr könnt mir bei diesen Fragen helfen.
grüße
|
|
|
| |
|
Hallo steve.joke,
> Also um die b) zu verstehen, habe ich mir mal ein bsp. im
> internet angeschaut.
>
> http://www.physik-schule.de/download/pdf/Primzahl/Resteberechnung.pdf
>
>
> Hier berechnen die den Rest von [mm]2^{1000}[/mm] bei der Div durch
> 3.
>
> Die gehen dabei wie folgt vor:
>
> [mm]2\equiv[/mm] 2 mod 3
>
> Hier schon mal meine erste Frage, wie kommen die auf diese
> Zeile?? Ok, die erste 2 kommt von [mm]2^{1000}[/mm] und durch 3 wird
> geteilt, aber wie kommen die dann auf die zweit 2 hinter
> dem [mm]\equiv[/mm] ??
Es werden hier sämtliche 2er-Potenzen mod 3 berechnet.
Das fängt an mit
[mm]2^{1}=2 \ \operatorname{mod} \ 3[/mm]
>
> [mm]2\equiv[/mm] 2 mod 3
>
> [mm]2^2=4=3*1+1 \equiv[/mm] 1 mod 3
>
> Hier genauso, wie kommen die von 3*1+1 auf [mm]\equiv[/mm] 1 mod
> 3???
Weil 3*1 durch 3 teilbar ist, ist [mm]3*1+1 \equiv \ 1 \operatorname{mod} \ 3[/mm].
>
> [mm]2^3\equiv[/mm] 2 mod 3
>
> [mm]2^4\equiv 4\equiv[/mm] 1 mod 3
>
> wieso ist hier auf einmal [mm]2^4\equiv[/mm] 4??
[mm]2^4 = 2^3*2 \equiv 2*2=4 \equiv \ 1 \operatorname{mod} \ 3[/mm]
>
> und daraus folgt dann [mm]2^{1000}\equiv[/mm] 1 mod 3, also ist der
> Rest 1.
>
>
> Hoffe, ihr könnt mir bei diesen Fragen helfen.
>
> grüße
Gruss
MathePower
|
|
|
| |
|
Hmm, ok. dann zurück zu meiner Aufgabe, wo der Rest von [mm] 2^{81} [/mm] bei der Div. durch 5 gesucht ist.
Fange wie oben an
[mm] 2^1 \equiv [/mm] 2 mod 5
[mm] 2^2=4 \equiv [/mm] 2 mod 5
[mm] 2^3=8=5*1+3 \equiv [/mm] 3 mod 5
[mm] 2^4=2^3 2^1 \equiv [/mm] 3*2 [mm] \equiv [/mm] 6 mod 5
[mm] 2^5=2^3 2^2 \equiv [/mm] 3*2 [mm] \equiv [/mm] 6 mod 5
[mm] 2^6=2^32^3 \equiv [/mm] 3*3 [mm] \equiv [/mm] 9 mod 5
So und bei diesem letzten Schritt könnte ich ja auch sagen
[mm] 2^6=2^42^2 \equiv [/mm] 6*2 [mm] \equiv [/mm] 12 mod 5
Damit hätte ich ja dann zwei unterschiedliche Ergebnisse :-/
stimmt das überhaupt alles so, wie ich es gemacht habe??
Und außerdem würde es in diesem Fall auch irgendwie viel zu lange dauern, so vorzugehen. Geht das vielleicht irgendwie noch schneller???
|
|
|
| |
|
Hallo nochmal,
> Hmm, ok. dann zurück zu meiner Aufgabe, wo der Rest von
> [mm]2^{81}[/mm] bei der Div. durch 5 gesucht ist.
>
> Fange wie oben an
>
> [mm]2^1 \equiv[/mm] 2 mod 5
>
> [mm]2^2=4 \equiv[/mm] 2 mod 5
>
> [mm]2^3=8=5*1+3 \equiv[/mm] 3 mod 5
>
> [mm]2^4=2^3 2^1 \equiv[/mm] 3*2 [mm]\equiv[/mm] 6 mod 5
>
> [mm]2^5=2^3 2^2 \equiv[/mm] 3*2 [mm]\equiv[/mm] 6 mod 5
>
> [mm]2^6=2^32^3 \equiv[/mm] 3*3 [mm]\equiv[/mm] 9 mod 5
>
> So und bei diesem letzten Schritt könnte ich ja auch
> sagen
>
> [mm]2^6=2^42^2 \equiv[/mm] 6*2 [mm]\equiv[/mm] 12 mod 5
>
> Damit hätte ich ja dann zwei unterschiedliche Ergebnisse
> :-/
>
> stimmt das überhaupt alles so, wie ich es gemacht habe??
Es ist [mm]\operatorname{ggT}(2,5)=1[/mm], also mit Euler
[mm]2^{\varphi(5)}\equiv 1 \ (\operatorname{mod}5)[/mm]
Dh. [mm]2^4\equiv 1 (\operatorname{mod}5)[/mm]
Weiter ist [mm]2^{81}=2\cdot{}2^{80}=\red{2}\cdot{}\left(2^4\right)^{20}[/mm]
Also [mm]2^{81}\equiv \red{2}\cdot{}1^{20}=2 \ (\operatorname{mod}5)[/mm]
[mm]2^{81}[/mm] lässt also Rest 2 bei Division durch 5 ...
>
> Und außerdem würde es in diesem Fall auch irgendwie viel
> zu lange dauern, so vorzugehen. Geht das vielleicht
> irgendwie noch schneller???
>
Gruß
schachuzipus
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 22:31 Di 24.05.2011 | | Autor: | steve.joke |
Vielen Dank.
Das war so natürlich viel einfacher.
Grüße
|
|
|
| |
|
Hallo nochmal,
> Hmm, ok. dann zurück zu meiner Aufgabe, wo der Rest von
> [mm]2^{81}[/mm] bei der Div. durch 5 gesucht ist.
>
> Fange wie oben an
>
> [mm]2^1 \equiv[/mm] 2 mod 5
>
> [mm]2^2=4 \equiv[/mm] 2 mod 5
Hier liegt der Hund begraben, es lässt 4 bei Division durch 5 doch Rest 4 und nicht 2, also [mm]2^2\equiv 4 \ (\operatorname{mod}5)[/mm]
>
> [mm]2^3=8=5*1+3 \equiv[/mm] 3 mod 5
>
> [mm]2^4=2^3 2^1 \equiv[/mm] 3*2 [mm]\equiv[/mm] 6 mod 5
>
> [mm]2^5=2^3 2^2 \equiv[/mm] 3*2 [mm]\equiv[/mm] 6 mod 5 ![[notok]](/images/smileys/notok.gif "[notok]")
Folgefehler, richtig [mm]...\equiv 3\cdot{}4=12\equiv 2 \ (\operatorname{mod}5)[/mm]
>
> [mm]2^6=2^32^3 \equiv[/mm] 3*3 [mm]\equiv[/mm] 9 mod 5
Weiter vereinfacht: [mm]9\equiv 4 \ (\operatorname{mod}5)[/mm]
>
> So und bei diesem letzten Schritt könnte ich ja auch
> sagen
>
> [mm]2^6=2^42^2 \equiv[/mm] 6*2 [mm]\equiv[/mm] 12 mod 5
Folgefehler ... [mm]...\equiv 1\cdot4[/mm] (oder auch [mm]6\cdot{}4[/mm]) [mm]\equiv 4 \ (\operatorname{mod}5)[/mm]
>
> Damit hätte ich ja dann zwei unterschiedliche Ergebnisse
Nicht wirklich 
> :-/
>
> stimmt das überhaupt alles so, wie ich es gemacht habe??
>
> Und außerdem würde es in diesem Fall auch irgendwie viel
> zu lange dauern, so vorzugehen. Geht das vielleicht
> irgendwie noch schneller???
>
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 23:24 Di 24.05.2011 | | Autor: | steve.joke |
Hi danke für deine korrektur,
hatte das echt nicht gemerkt.
aber diesen weg würde man wohl auch zum ziel kommen, oder??
nur ist der wohl bisschen mühseliggggg
grüße
|
|
|
|
