Rest der Division bestimmen < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 15:30 So 18.12.2011 | | Autor: | HannSG |
| Aufgabe | | Bestimmen Sie den Rest der Division der Zahl [mm] 19^{42}*23^{51} [/mm] durch 7 |
Hallo,
Meine Idee:
Da die Division einen Rest lässt, gilt 7 teilt nicht [mm] 19^{42}*23^{51}. [/mm]
[mm] \Rightarrow ggT(19^{42}*23^{51}, [/mm] 7)=1
D.h. wir können den kleinen Satz von Fermat anwenden.
[mm] (19^{42}*23^{51})^{(7-1)}\equiv1 [/mm] mod 7
Ist das bis hier hin so sinnvoll und richtig?
Ich habe auch ein bisschen umgeformt, aber ich finde noch keinen Weg, den Ausdruck so vereinfachen darzustellen, dass der Rest sichtbar wird.
Vielen Dank schonmal!
Lg HannSG
|
|
| |
|
Hallo,
also ich habe da so eine Idee. Weiß aber nicht 100%-ig, ob das zum Ziel führt. Also ich würde mir jeweils die letzte Stelle von [mm]19, 19^2, 19^3 ...[/mm] und [mm]23, 23^2, 23^3 ...[/mm] betrachten. Falls sich eine Endung wiederholt, musst du den Exponenten betrachten und ihn mit deinen Potenzen in der Aufgabebstellung vergleichen. Vielleicht ist ja der eine Exponent ein Vielfaches des anderen. Somit könntest du dir dann mit der kleineren Potenz das Ergebnis herleiten.
Gruß
Christoph
|
|
|
| |
|
Sorry meine Vermutung ist falsch.
Gruß
Christoph
|
|
|
| |
|
> Bestimmen Sie den Rest der Division der Zahl
> [mm]19^{42}*23^{51}[/mm] durch 7
> Hallo,
>
> Meine Idee:
> Da die Division einen Rest lässt, gilt 7 teilt nicht
> [mm]19^{42}*23^{51}.[/mm]
> [mm]\Rightarrow ggT(19^{42}*23^{51},[/mm] 7)=1
> D.h. wir können den kleinen Satz von Fermat anwenden.
>
> [mm](19^{42}*23^{51})^{(7-1)}\equiv1[/mm] mod 7
> Ist das bis hier hin so sinnvoll und richtig?
>
> Ich habe auch ein bisschen umgeformt, aber ich finde noch
> keinen Weg, den Ausdruck so vereinfachen darzustellen, dass
> der Rest sichtbar wird.
>
> Vielen Dank schonmal!
> Lg HannSG
>
Der Lösungsansatz ist, [mm] 19^{42} [/mm] mod 7 und [mm] 23^{51} [/mm] mod 7 getrennt zu berechnen. Dabei kann jeweils der Satz von Fermat benutzt werden.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 12:54 Mo 19.12.2011 | | Autor: | HannSG |
Das verstehe ich noch nicht ganz.
Wie soll ich denn [mm] 19^{42} [/mm] mod 7 und [mm] 23^{51} [/mm] mod 7 mit dem kleinen Satz von Fermat berechnen?
Muss ich dann mit [mm] 19^{42}\equiv1 [/mm] mod 7 und [mm] 23^{51}\equiv1 [/mm] mod 7 anfangen?
|
|
|
| |
|
Hallo,
> Das verstehe ich noch nicht ganz.
> Wie soll ich denn [mm]19^{42}[/mm] mod 7 und [mm]23^{51}[/mm] mod 7 mit dem
> kleinen Satz von Fermat berechnen?
>
> Muss ich dann mit [mm]19^{42}\equiv1[/mm] mod 7 und [mm]23^{51}\equiv1[/mm]
> mod 7 anfangen?
Anfangen ist übertrieben, ersteres sieht man ja schnell ein, aber wieso ist denn [mm]23^{51} \ \equiv \ 1 \ \operatorname{mod}(7)[/mm]
Erstmal ist doch für [mm]\operatorname{ggT}(a,n)=1[/mm]: [mm]a^{\varphi(n)} \ \equiv \ 1 \ \operatorname{mod}(n)[/mm]
Hier sind 19 und 7 teilerfremd, 7 ist prim, also [mm]\varphi(7)=6[/mm]
Damit hast du [mm]19^6 \ \equiv \ 1 \ \operatorname{mod}(7)[/mm]
Und [mm]19^{42}=\left(19^6\right)^7[/mm]
Also [mm]19^{42} \ \equiv \ 1^{7} \ = \ 1 \ \operatorname{mod}(7)[/mm]
Ganz ähnlich gehe bei dem anderen Faktor vor, dort ist die Zerlegung des Exponenten aber nicht ganz so einfach wie beim ersten Faktor.
Gruß
schachuzipus
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 14:47 Mo 19.12.2011 | | Autor: | HannSG |
Kann man das nicht parallel für [mm] 23^{51} [/mm] machen?
[mm] (23^{6})^{ 8,5}\equiv1^{8,5} [/mm] mod 7
Oder dürfen wir nur mit natürlichen Zahlen rechnen?
Lg
Hanna
|
|
|
| |
|
Hallo Hanna,
> Kann man das nicht parallel für [mm]23^{51}[/mm] machen?
>
> [mm](23^{6})^{ 8,5}\equiv1^{8,5}[/mm] mod 7
>
> Oder dürfen wir nur mit natürlichen Zahlen rechnen?
Ja! *Ich* kenne die Regel nur für nat. Zahen:
Hilfreich könnte sein: [mm]23^{51}=23^{3+48}=23^3\cdot{}23^{48}[/mm]
Der hintere Faktor ist nun leicht kaputtzuschlagen, für [mm]23^3[/mm] nutze aus, dass [mm]23 \ \equiv \ 2 \ \operatorname{mod}(7)[/mm]
>
> Lg
> Hanna
Gruß
schachuzipus
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 15:23 Mo 19.12.2011 | | Autor: | HannSG |
[mm] 23^{6} \equiv1 [/mm] mod 7 [mm] \gdw 23^{48} \equiv1^{8} [/mm] mod 7 [mm] \gdw 23^{48} \equiv1 [/mm] mod 7
[mm] 23^{3}: [/mm] 23 [mm] \equiv2 [/mm] mod 7 [mm] \gdw 23^{3} \equiv8 [/mm] mod 7
Woher weiß ich denn ohne Taschenrechner, dass 2:7 den selben Rest wie 23:7 hat?
Kann man das so getrennt berechnen? Und was sagt mir das jetzt über den Rest?
Danke.
Lg Hanna
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 15:29 Mo 19.12.2011 | | Autor: | fred97 |
> [mm]23^{6} \equiv1[/mm] mod 7 [mm]\gdw 23^{48} \equiv1^{8}[/mm] mod 7 [mm]\gdw 23^{48} \equiv1[/mm]
> mod 7
>
> [mm]23^{3}:[/mm] 23 [mm]\equiv2[/mm] mod 7 [mm]\gdw 23^{3} \equiv8[/mm] mod 7
>
> Woher weiß ich denn ohne Taschenrechner, dass 2:7 den
> selben Rest wie 23:7 hat?
23=21+2=3*7+2
FRED
> Kann man das so getrennt berechnen? Und was sagt mir das
> jetzt über den Rest?
>
> Danke.
> Lg Hanna
|
|
|
| |
|
Hallo Hanna,
bitte nicht den Status einer Frage kommenarlos ändern!
Das ist kein guter Ton und wird gar nicht gerne gesehen.
Wenn du noch Fragen hast, stelle sie als weitere Fragen.
Du musst letztlich nur alles zusammensetzen, was wir bisher herausgefunden haben.
[mm]19^{42}\cdot{}23^{51} \ = \ \left(19^6\right)^7\cdot{}23^3\cdot{}\left(23^6\right)^8 \ \equiv \ 1^7\cdot{}2^3\cdot{}1^8 \ = \ 8 \ \equiv \ ... \ \operatorname{mod}(7)[/mm]
Gruß
schachuzipus
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 16:19 Mo 19.12.2011 | | Autor: | HannSG |
Tut mir Leid. Das wusste ich nicht und es war auch nicht böse gemeint.
Danke für die Hilfe.
Lg Hanna
|
|
|
|
