hohe Potenzen + modulo lösen < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Ermitteln Sie die letzten beiden Ziffern der Zahlen
a) [mm] 3^{1003}
[/mm]
b) [mm] 7^7^7^7 [/mm] - [mm] 7^7^7
[/mm]
Lösen Sie die Aufgabe mittels Kongruenzrechnung. |
Hi,
ich weiß nicht wirklich wie ich diese Aufgabe lösen kann. Ich musss doch modulo100 rechnen, wegen der letzten beiden Ziffern, oder?
Also hätte ich dann bei a):
[mm] 3^{1003} [/mm] mod 100 = [mm] (3^{1000}*3^3) [/mm] mod 100 = [mm] 3^{1000} [/mm] mod [mm] 100*3^3 [/mm] mod 100 evtl. noch = [mm] 3^{100}^{10} [/mm] mod [mm] 100*3^3 [/mm] mod 100
Wie kann ich nun weitermachen? Bringt mir das was, dass ich im Exponenten meine Restklasse stehen habe?
Dank und Gruß
congo
|
|
| |
|
Hallo congo.hoango,
> Ermitteln Sie die letzten beiden Ziffern der Zahlen
>
> a) [mm]3^{1003}[/mm]
>
> b) [mm]7^7^7^7[/mm] - [mm]7^7^7[/mm]
>
> Lösen Sie die Aufgabe mittels Kongruenzrechnung.
> Hi,
>
> ich weiß nicht wirklich wie ich diese Aufgabe lösen kann.
> Ich musss doch modulo100 rechnen, wegen der letzten beiden Ziffern, oder?
Ja.
>
> Also hätte ich dann bei a):
>
> [mm]3^{1003}[/mm] mod 100 = [mm](3^{1000}*3^3)[/mm] mod 100 = [mm]3^{1000}[/mm] mod [mm]100*3^3[/mm] mod 100 evtl. noch = [mm]3^{100}^{10}[/mm] mod [mm]100*3^3[/mm] mod 100
>
> Wie kann ich nun weitermachen? Bringt mir das was, dass ich
> im Exponenten meine Restklasse stehen habe?
Berechne erstmal [mm] 3^n [/mm] mod 100 für kleine n. Du wirst feststellen, dass [mm] 3^{20}\equiv [/mm] 1 mod 100 und dann ist der Rest nicht mehr schwer.
bei der b) gehst du genauso vor und schaust dir erstmal [mm] 7^n [/mm] mod 100 für kleine n an. Da wirst du sogar für noch kleineres n feststellen, dass [mm] 7^n\equiv1 [/mm] mod 100 ist.
LG
|
|
|
| |
|
> Berechne erstmal [mm]3^n[/mm] mod 100 für kleine n. Du wirst
> feststellen, dass [mm]3^{20}\equiv[/mm] 1 mod 100 und dann ist der
> Rest nicht mehr schwer.
Ok, danke! Und wie immer, meine Frage: Gibts da Tricks um die Ordnung von 3 in [mm] \IZ_{100} [/mm] auszurechnen? (Weil ich in der Klausur keinen Taschenrechner nutzen darf meine ich...). Bis ich da auf [mm] 3^{20} [/mm] gekommen bin, würde das doch schon ein bisschen dauern, wenn ich das "per Hand" bestimmen möchte...
> bei der b) gehst du genauso vor und schaust dir erstmal [mm]7^n[/mm]
> mod 100 für kleine n an. Da wirst du sogar für noch
> kleineres n feststellen, dass [mm]7^n\equiv1[/mm] mod 100 ist.
Ok, dank dir! Hat mir wirklich sehr geholfen.
Gruß
congo
|
|
|
| |
|
Hallo congo,
> > Berechne erstmal [mm]3^n[/mm] mod 100 für kleine n. Du wirst
> > feststellen, dass [mm]3^{20}\equiv[/mm] 1 mod 100 und dann ist der
> > Rest nicht mehr schwer.
>
> Ok, danke! Und wie immer, meine Frage: Gibts da Tricks um
> die Ordnung von 3 in [mm]\IZ_{100}[/mm] auszurechnen? (Weil ich in
> der Klausur keinen Taschenrechner nutzen darf meine
> ich...). Bis ich da auf [mm]3^{20}[/mm] gekommen bin, würde das
> doch schon ein bisschen dauern, wenn ich das "per Hand"
> bestimmen möchte...
Du kennst doch bestimmt den ![[]](/images/popup.gif) Satz von Euler-Fermat. Der ist hier nicht nur praktisch, sondern nötig. Hier ist [mm] \varphi(100)=20.
[/mm]
Die Ordnung einer zum Modul n teilerfremden Zahl ist immer ein echter Teiler von [mm] \varphi(n).
[/mm]
Für n=100 ist z.B. $ ord(49)=2, ord(7)=4, ord(21)=5, ord(11)=10, ord(3)=20 $.
Du siehst, es sind alle echten Teiler vertreten (und $ ord(1)=1 $ ist trivial).
Sooo viel probieren muss man also gar nicht.
Grüße
reverend
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 18:58 Mi 20.07.2011 | | Autor: | reverend |
Hallo congo,
ich bin halt schwach im Kopfrechnen...
reverend
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 19:16 Mi 20.07.2011 | | Autor: | felixf |
Moin rev,
> ich bin halt schwach im Kopfrechnen...
vielleicht hat dein Kopf ja auch einfach an den Exponenten der multiplikativen Gruppe gedacht anstelle an deren Ordnung
20 ist (als kgV von [mm] $\phi(5^2)$ [/mm] und [mm] $\phi(2^2)$) [/mm] die kleinste Zahl $n$ mit [mm] $a^n \equiv [/mm] 1 [mm] \pmod{100}$ [/mm] fuer alle $a$, die teilerfremd zu $100$ sind.
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 19:49 Mi 20.07.2011 | | Autor: | reverend |
Hallo Felix,
> vielleicht hat dein Kopf ja auch einfach an den Exponenten
> der multiplikativen Gruppe gedacht anstelle an deren
> Ordnung
>
> 20 ist (als kgV von [mm]\phi(5^2)[/mm] und [mm]\phi(2^2)[/mm]) die kleinste
> Zahl [mm]n[/mm] mit [mm]a^n \equiv 1 \pmod{100}[/mm] fuer alle [mm]a[/mm], die
> teilerfremd zu [mm]100[/mm] sind.
Ein hübscher Rettungsversuch. Wenn ich das aber tatsächlich irgendwie im Hinterkopf gehabt haben sollte, dann hätte ich doch mehr Überreste meiner vergangenen Zahlentheorie, als ich glaube. Bewusst war mir dieser Zusammenhang jedenfalls definitiv nicht (mehr? ich zweifle daran).
Grüße
reverend
|
|
|
| |
|
> 20 ist (als kgV von [mm]\phi(5^2)[/mm] und [mm]\phi(2^2)[/mm]) die kleinste
> Zahl [mm]n[/mm] mit [mm]a^n \equiv 1 \pmod{100}[/mm] fuer alle [mm]a[/mm], die
> teilerfremd zu [mm]100[/mm] sind.
Kann ich das immer so machen? Also ord a mod b = [mm] kgV(\phi(p_1^k), [/mm] ... , [mm] \phi(p_n^l))?
[/mm]
Weil bei der b) - Aufgabe stehe ich vor dem Problem, dass mich der 40er-Exponent nicht so wirklich weiterbringt.
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 01:17 Do 21.07.2011 | | Autor: | felixf |
Moin!
> > 20 ist (als kgV von [mm]\phi(5^2)[/mm] und [mm]\phi(2^2)[/mm]) die kleinste
> > Zahl [mm]n[/mm] mit [mm]a^n \equiv 1 \pmod{100}[/mm] fuer alle [mm]a[/mm], die
> > teilerfremd zu [mm]100[/mm] sind.
>
> Kann ich das immer so machen? Also ord a mod b =
> [mm]kgV(\phi(p_1^k),[/mm] ... , [mm]\phi(p_n^l))?[/mm]
Nein - die Ordnung ist im Allgemeinen nur ein Teiler davon. Aber: es gibt immer ein $a$, dessen Ordnung gleich dem kgV ist.
> Weil bei der b) - Aufgabe stehe ich vor dem Problem, dass
> mich der 40er-Exponent nicht so wirklich weiterbringt.
Wieso? Damit hast du schonmal Exponenten $< 40$. Dann kommst du mit Quadrieren und Multiplizieren gut weiter.
LG Felix
|
|
|
| |
|
Das ist ja auch nicht so wichtig, wie das mathematische Denken  Mein Prof verrechnet sich auch oft.
|
|
|
| |
|
> Das ist ja auch nicht so wichtig, wie das mathematische
> Denken Mein Prof verrechnet sich auch oft.
Dann ist es ja wohl gut, dass er Professor geworden ist und nicht zum Beispiel Buchhalter oder Ingenieur oder Laborant oder Anästhesiearzt !
|
|
|
| |
|
Wollte nochmal meine fertigen Lösungen reinstellen und fragen ob so alles korrekt ist:
zu a)
Ges: letzten zwei Ziffern von [mm] 3^{1003} [/mm]
[mm] \varphi(100)=40 [/mm]
[mm] \Rightarrow [/mm] ord3mod100 | 40
[mm] \Rightarrow [/mm] ord3mod100 [mm] \in \{40,20,10,8,5,4,2,1\}
[/mm]
[mm] \overline{3}^1 \not= \overline{1}
[/mm]
[mm] \overline{3}^2 \not= \overline{1}
[/mm]
[mm] \overline{3}^4 \not= \overline{1}
[/mm]
[mm] \overline{3}^5 \not= \overline{1}
[/mm]
[mm] \overline{3}^8 \not= \overline{1}
[/mm]
[mm] \overline{3}^{10} \not= \overline{1}
[/mm]
[mm] \overline{3}^{20} [/mm] = [mm] \overline{1}
[/mm]
[mm] {\overline{3}}^{1003}={\overline{3}}^{1000}*{\overline{3}}^3=\overlin{3}^3=\overline{27}
[/mm]
[mm] \Rightarrow [/mm] die letzten beiden Ziffern von [mm] 3^{1003} [/mm] lauten 27
zu b):
Ich gehe vor wie oben, komme auf ord7mod100=4
[mm] \Rightarrow {{{\overline{7}^7}^7}^7}-{\overline{7}^7}^7={\overline{7}^{49}}^7-\overline{7}^{49}=(\overline{7}^{48}*\overline{7})^7-\overline{7}^{48}*\overline{7}=\overline{7}^3-\overline{7}=\overline{36}
[/mm]
[mm] \Rightarrow [/mm] letzten beiden Ziffern sind 36
Habe ich alles richtig gemacht?
Vielen Dank nochmal für eure Hilfe, insbesondere dieser Algorthmus für die Exponentialrechnung hat mir sehr weitergeholfen, den kannte ich gar nicht.
Gruß
congo
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 14:54 Do 21.07.2011 | | Autor: | felixf |
Moin!
> Wollte nochmal meine fertigen Lösungen reinstellen und
> fragen ob so alles korrekt ist:
>
> zu a)
>
> Ges: letzten zwei Ziffern von [mm]3^{1003}[/mm]
>
> [mm]\varphi(100)=40[/mm]
>
> [mm]\Rightarrow[/mm] ord3mod100 | 40
> [mm]\Rightarrow[/mm] ord3mod100 [mm]\in \{40,20,10,8,5,4,2,1\}[/mm]
>
> [mm]\overline{3}^1 \not= \overline{1}[/mm]
> [mm]\overline{3}^2 \not= \overline{1}[/mm]
>
> [mm]\overline{3}^4 \not= \overline{1}[/mm]
> [mm]\overline{3}^5 \not= \overline{1}[/mm]
>
> [mm]\overline{3}^8 \not= \overline{1}[/mm]
> [mm]\overline{3}^{10} \not= \overline{1}[/mm]
>
> [mm]\overline{3}^{20}[/mm] = [mm]\overline{1}[/mm]
>
>
> [mm]{\overline{3}}^{1003}={\overline{3}}^{1000}*{\overline{3}}^3=\overlin{3}^3=\overline{27}[/mm]
>
> [mm]\Rightarrow[/mm] die letzten beiden Ziffern von [mm]3^{1003}[/mm] lauten
> 27
![[ok]](/images/smileys/ok.gif "[ok]")
> zu b):
>
> Ich gehe vor wie oben, komme auf ord7mod100=4
>
> [mm]\Rightarrow {{{\overline{7}^7}^7}^7}-{\overline{7}^7}^7={\overline{7}^{49}}^7-\overline{7}^{49}=(\overline{7}^{48}*\overline{7})^7-\overline{7}^{48}*\overline{7}=\overline{7}^3-\overline{7}=\overline{36}[/mm]
Das stimmt so nicht: [mm] $7^{7^7}$ [/mm] ist nicht [mm] $49^7$, [/mm] sondern [mm] $7^{49}$.
[/mm]
LG Felix
|
|
|
| |
|
> Das stimmt so nicht: [mm]7^{7^7}[/mm] ist nicht [mm]49^7[/mm], sondern [mm]7^{49}[/mm].
Das stimmt aber so auch noch nicht ...
[mm]7^{7^7}\ =\ 7^{\left(7^7\right)}\ =\ 7^{823543}[/mm]
Gruß Al
|
|
|
| |
|
Die Lösung für [mm] 3^{1003} [/mm] stimmt.
Als zweite Zahl hatten wir aber doch ursprünglich [mm] 7^{777}-7^{77} [/mm] , oder nicht ?
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 15:08 Do 21.07.2011 | | Autor: | felixf |
Moin!
> Als zweite Zahl hatten wir aber doch ursprünglich
> [mm]7^{777}-7^{77}[/mm] , oder nicht ?
Ja. Stimmt. Genauso wie dein anderer Einwand.
Ich glaube ich geh gleich nach Hause und mach erstmal eine Zeit was anderes, bevor ich mich wieder an Mathematik wage...
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 20:29 Do 21.07.2011 | | Autor: | reverend |
Hallo Felix (und alle anderen),
> Ich glaube ich geh gleich nach Hause und mach erstmal eine
> Zeit was anderes, bevor ich mich wieder an Mathematik
> wage...
Das ist in vielen Fächern nötig. Wenn Du Dein eigenes Werkzeug bist, dann musst Du halt auch zusehen, dass es "scharf" bleibt.
Freizeit ist darum nötig, um sich vernünftig für die Arbeit vorzubereiten.
wzbw.
(was zu beachten wäre!)
Grüße
reverend
|
|
|
| |
|
| Status: |
(Frage) beantwortet  | | Datum: | 14:17 Di 26.07.2011 | | Autor: | peter_k |
Hallo,
ich habe eine Frage gleicher Bauart und wollte Fragen ob meine Rechnung so richtig ist. Es geht auch darum die letzten beiden Ziffern zu bestimmen:
[mm] 13^{{39}^{26}}
[/mm]
ord13mod100=3 [mm] \Rightarrow13^{{39}^{26}}=13^1 \Rightarrow [/mm] die letzten beiden Ziffern sind 13.
Kommt mir aber irgendwie ein bisschen kurz vor der Lösungsweg. Ist das richtig?
Gruß
Peter
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 14:29 Di 26.07.2011 | | Autor: | statler |
Hi!
> ich habe eine Frage gleicher Bauart und wollte Fragen ob
> meine Rechnung so richtig ist. Es geht auch darum die
> letzten beiden Ziffern zu bestimmen:
>
> [mm]13^{{39}^{26}}[/mm]
>
> ord13mod100=3 [mm]\Rightarrow13^{{39}^{26}}=13^1 \Rightarrow[/mm]
> die letzten beiden Ziffern sind 13.
>
> Kommt mir aber irgendwie ein bisschen kurz vor der
> Lösungsweg. Ist das richtig?
ord13mod100=3 kann ich nicht glauben, da [mm] 3^3 \equiv [/mm] 7 mod 10 ist. Oder haben wir unterschiedliche Nomenklaturen?
Gruß aus HH-Harburg
Dieter
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 14:34 Di 26.07.2011 | | Autor: | peter_k |
ja hast Recht, ich zieh die Frage erstmal wieder zurück und melde mich wieder wenn ich das nochmal "überarbeitet" habe
Gruß
Peter
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 15:06 Di 26.07.2011 | | Autor: | peter_k |
Alsooo, habe nochmal nachgerechnet und bin auf ord13mod100=20 gekommen. Aber da habe ich ja noch einen Fehler gemacht oder?
Ich müsste doch vorerst noch den Exponenten von 13 berechnen, also [mm] 39^{26} [/mm] oder? Das darf ich doch aber nicht mod100 rechnen oder?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 15:18 Di 26.07.2011 | | Autor: | statler |
Hallooo!
> Alsooo, habe nochmal nachgerechnet und bin auf
> ord13mod100=20 gekommen. Aber da habe ich ja noch einen
> Fehler gemacht oder?
Das ist OK, oder wir haben uns beide verrechnet.
> Ich müsste doch vorerst noch den Exponenten von 13
> berechnen, also [mm]39^{26}[/mm] oder? Das darf ich doch aber nicht
> mod100 rechnen oder?
Jetzt weißt du, daß 13 hoch ein Vielfaches von 20 auf 01 endet. Also brauchst du vom Exponenten seinen Rest mod 20. Das ist nicht so schwer, weil 39 [mm] \equiv [/mm] -1 mod 20 ist.
Gruß
Dieter
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 15:44 Di 26.07.2011 | | Autor: | peter_k |
> Jetzt weißt du, daß 13 hoch ein Vielfaches von 20 auf 01
> endet. Also brauchst du vom Exponenten seinen Rest mod 20.
> Das ist nicht so schwer, weil 39 [mm]\equiv[/mm] -1 mod 20 ist.
Also da [mm] 39mod(ord13mod100=20)\equiv-1 [/mm] folgt [mm] 13^{{39}^{16}}=13^{{-1}^{26}}=13
[/mm]
Ist das so korrekt? Ich bi noch ein wenig verwirrt was modulo was ist...
Gruß
Peter
|
|
|
| |
|
Hallo peter_k,
> > Jetzt weißt du, daß 13 hoch ein Vielfaches von 20 auf 01
> > endet. Also brauchst du vom Exponenten seinen Rest mod 20.
> > Das ist nicht so schwer, weil 39 [mm]\equiv[/mm] -1 mod 20 ist.
>
> Also da [mm]39mod(ord13mod100=20)\equiv-1[/mm] folgt
> [mm]13^{{39}^{16}}=13^{{-1}^{26}}=13[/mm]
>
> Ist das so korrekt? Ich bi noch ein wenig verwirrt was
Ja.
> modulo was ist...
Das ist die "Division mit Rest".
>
> Gruß
> Peter
Gruss
MathePower
|
|
|
| |
|
> Alsooo, habe nochmal nachgerechnet und bin auf
> ord13mod100=20 gekommen. Aber da habe ich ja noch einen
> Fehler gemacht oder?
> Ich müsste doch vorerst noch den Exponenten von 13
> berechnen, also [mm]39^{26}[/mm] oder? Das darf ich doch aber nicht
> mod100 rechnen oder?
Eigentlich dann mod 20 ; aber wenn du zunächst mod 100
probieren willst, bringt dich dies auch weiter wegen 100=5*20
LG
|
|
|
|
![[notok]](/images/smileys/notok.gif "[notok]"){kind=small}
