www.vorhilfe.de
- Förderverein -
Der Förderverein.

Gemeinnütziger Verein zur Finanzierung des Projekts Vorhilfe.de.
Hallo Gast!einloggen | registrieren ]
Startseite · Mitglieder · Impressum
Forenbaum
^ Forenbaum
Status VH e.V.
  Status Vereinsforum

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Suchen
 Impressum
Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
Forum "Zahlentheorie" - Rest bei Division durch 22
Rest bei Division durch 22 < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Zahlentheorie"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Rest bei Division durch 22: Frage (beantwortet)
Status: (Frage) beantwortet Status 
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!

        
Bezug
Rest bei Division durch 22: Antwort (fehlerhaft)
Status: (Antwort) fehlerhaft Status 
Datum: 16:33 Mi 08.02.2006
Autor: banachella

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

Bezug
                
Bezug
Rest bei Division durch 22: Antwort
Status: (Antwort) fertig Status 
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


Bezug
        
Bezug
Rest bei Division durch 22: Idee Korrektur?
Status: (Antwort) fertig Status 
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 =)

Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Zahlentheorie"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
ev.vorhilfe.de
[ Startseite | Mitglieder | Impressum ]