Rest bei Division durch 22 < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 20:39 Di 07.02.2006 | | Autor: | wilma |
| Aufgabe | | Welchen rest lässt [mm] 1234567890^{1234567890} [/mm] bei Division durch 22? |
Guten Abend,
ich fände es super, wenn mir jemand bei dieser Aufgabenstellung helfen könnte. Ich komme einfach nicht zur Lösung.
Danke!
|
|
| |
|
Hallo!
Der Trick ist, in [mm] $\IZ/22\IZ$ [/mm] zu rechnen:
[mm] $1234567890\mod [/mm] 22=6$. Dann gilt:
[mm] $1234567890^{1234567890} \mod\ 22=(6+22*a)^{6+22*a}\mod\ 22\equiv 6^6\mod 22\equiv [/mm] 14$.
Hundertprozentig sicher bin ich mir nicht, dafür ist das bei mir auch schon alles zu lange her. Aber ich glaube schon, dass das stimmt...
Gruß, banachella
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 00:57 Do 20.07.2006 | | Autor: | felixf |
Hallo Banachella!
> Der Trick ist, in [mm]\IZ/22\IZ[/mm] zu rechnen:
> [mm]1234567890\mod 22=6[/mm]. Dann gilt:
> [mm]1234567890^{1234567890} \mod\ 22=(6+22*a)^{6+22*a}\mod\ 22\equiv 6^6\mod 22\equiv 14[/mm].
>
> Hundertprozentig sicher bin ich mir nicht, dafür ist das
> bei mir auch schon alles zu lange her. Aber ich glaube
> schon, dass das stimmt...
Nee, leider nicht. Wenn du [mm] $a^b \mod{n}$ [/mm] hast, dann darfst du $b$ nicht modulo $n$ aendern, sondern nur modulo [mm] $\phi(n)$ [/mm] (Eulersche [mm] $\phi$-Funktion). [/mm] Und nun ist [mm] $\phi(22) [/mm] = [mm] \phi(11) \phi(2) [/mm] = (11 - 1) (2 - 1) = 10$, womit du den Exponenten modulo 10 und nicht modulo 22 nehmen musst!
Allerdings tritt da noch ein weiters Problem auf, weshalb du gar nicht so einfach mit dem Exponenten rumspielen darfst: $ggT(1234567890, 22) > 1$, womit $1234567890$ keine Einheit in [mm] $\IZ/22$ [/mm] ist. Damit gilt der kleine Satz von Fermat in diesem Fall nicht und du darfst Exponenten von 1234567890 nicht einfach so kuerzen.
Wenn $1234567890 [mm] \equiv [/mm] 1 [mm] \pmod{10}$ [/mm] waere, so koenntest du mittels des Chinesischen Restsatzes zeigen, dass man trotzdem im Exponenten modulo rechnen darf (da 22 quadratfrei ist).
In diesem Fall geht das allerdings nicht so einfach. Du musst also das ganze mit dem Chin. Restsatz zerlegen und die Teile modulo 2 und modulo 11 betrachten.
Modulo 2 ist das ganze eh gleich 0. Und Modulo 11 ist es kongruent zu 6. Nun ist $6 + [mm] 11\IZ$ [/mm] eine Einheit in [mm] $\IZ/11$, [/mm] womit [mm] $6^{1234567890} \equiv 6^0 \equiv [/mm] 1 [mm] \pmod{11}$ [/mm] ist (da $1234567890 [mm] \equiv [/mm] 0 [mm] \pmod{10}$, [/mm] wobei $10 = [mm] \phi(11)$ [/mm] ist).
Jetzt musst du das Element $(0 + [mm] 2\IZ, [/mm] 1 + [mm] 11\IZ) \in \IZ/2 \times \IZ/11$ [/mm] wieder nach [mm] $\IZ/22$ [/mm] zurueckholen. Jedoch ist $12 [mm] \equiv [/mm] 0 [mm] \pmod{2}$, [/mm] $12 [mm] \equiv [/mm] 1 [mm] \pmod{11}$, [/mm] womit das zugehoerige Element in [mm] $\IZ/22$ [/mm] gerade $12 + [mm] 22\IZ$ [/mm] ist.
Also ist [mm] $1234567890^{1234567890} \equiv [/mm] 12 [mm] \pmod{22}$.
[/mm]
LG Felix
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 00:18 Do 20.07.2006 | | Autor: | gary06 |
ich komm aber irgendwie auf ein etwas anderes ergebnis
1234567890 = 2*5*3*3*13717421
bzw. 13717421 = 3607*3803 aba wayne
1234567890 mod 22 = 6
1234567890 mod 2 = 0 ---deswegen "scheiß" auf die 2 ^^
1234567890 mod 11 = 6 /
[mm] 6^2 [/mm] mod 11 = 14
[mm] 14^3 [/mm] mod 11 = 16
[mm] 16^3 [/mm] mod 11 = 4
[mm] 4^5 [/mm] mod 11 = 1 (!)
[mm] 1^{13717421} [/mm] mod 11 = 1
=>
[mm] 1234567890^{1234567890} [/mm] mod 22 = 12 =)
|
|
|
|
