Man bestimme 3^47 mod 23 < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 21:15 Mo 23.03.2009 | | Autor: | kaktus |
| Aufgabe | | Man bestimme [mm] 3^{47} [/mm] mod 23 |
Mit hilfe des kleinen Fermat soll das gelöst werden. Also ich habe schon mal umgeformt:
[mm] 3^{47} [/mm] = 3 * [mm] (3^{23} *3^{23})
[/mm]
aber darauf kann ich ja den kleinen Fermat nicht anwenden oder?
[mm] 3^{47} [/mm] = 3 mod 47 aber damit fange ich genau so wenig an ...
|
|
| |
|
Hallo Kaktus,
> Man bestimme [mm]3^{47}[/mm] mod 23
> Mit hilfe des kleinen Fermat soll das gelöst werden. Also
> ich habe schon mal umgeformt:
>
> [mm]3^{47}[/mm] = 3 * [mm](3^{23} *3^{23})[/mm]
>
> aber darauf kann ich ja den kleinen Fermat nicht anwenden
> oder?
Es ist doch 23 eine Primzahl und $ggT(3,23)=1$
Und für p prim und $ggT(a,p)=1$ gilt mit Fermat [mm] $a^{p-1}\equiv [/mm] 1 \ [mm] \mod [/mm] p$ ..,.
>
> [mm]3^{47}[/mm] = 3 mod 47 aber damit fange ich genau so wenig an
> ...
>
>
LG
schachuzipus
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 23:08 Mo 23.03.2009 | | Autor: | kaktus |
[mm] 3^{23} [/mm] * [mm] 3^{23} [/mm] = 3 * 3 mod 23 = 9 mod 23
aber wenn man [mm] 3^{47} [/mm] umformt hat man ja 3 * [mm] 3^{23} [/mm] * [mm] 3^{23} [/mm] und was ich mit dem der ersten 3 machen soll weiß ich nicht.
|
|
|
| |
|
Hallo nochmal,
> [mm]3^{23}[/mm] * [mm]3^{23}[/mm] = 3 * 3 mod 23 = 9 mod 23
>
> aber wenn man [mm]3^{47}[/mm] umformt hat man ja 3 * [mm]3^{23}[/mm] *
> [mm]3^{23}[/mm] und was ich mit dem der ersten 3 machen soll weiß
> ich nicht.
Hast du überhaupt gelesen, was ich geschrieben habe oder habe ich chinesisch geschrieben?
p=23 ist prim, dann ist doch wohl p-1=22
Also [mm] $3^{22}\equiv [/mm] 1 \ [mm] \mod [/mm] 23$
Damit [mm] $3^{44}=\left(3^{22}\right)^2\equiv 1^2=1 [/mm] \ [mm] \mod [/mm] 23$
Und damit dann [mm] $3^{47}=3^3\cdot{}3^{44}\equiv 3^3\cdot{}1=27\equiv [/mm] 4 \ [mm] \mod [/mm] 23$
Gruß
schachuzipus
|
|
|
| |
|
Hallo nochmal,
> [mm]3^{23}[/mm] * [mm]3^{23}[/mm] = 3 * 3 mod 23 = 9 mod 23
>
> aber wenn man [mm]3^{47}[/mm] umformt hat man ja 3 * [mm]3^{23}[/mm] *
> [mm]3^{23}[/mm] und was ich mit dem der ersten 3 machen soll weiß
> ich nicht.
Ah, jetzt sehe ich, was du meinst, sorry für meine harschen Worte in der anderen Antwort, aber zuerst war mir nicht ersichtlich, dass du auf den Tipp und überhauot den Satz von Fermat eingegangen bist.
Du hättest ein paar Worte spendieren können
Mit Fermat und den Rechenregeln für Kongruenzen ist in der Tat [mm] $3^{23}\cdot{}3^{23}\equiv [/mm] 9 \ [mm] \mod [/mm] 23$
Damit wie in der anderen Antwort: [mm] $3^{47}=3\cdot{}3^{23}\cdot{}3^{23}\equiv 3\cdot{}9=27\equiv [/mm] 4 \ [mm] \mod [/mm] 23$
LG
schachuzipus
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 12:30 Mi 25.03.2009 | | Autor: | kaktus |
genau da wollt ich drauf hinaus... ich war mir nicht sicher was ich mit der [mm] 3^1 [/mm] machen sollte da sie einen anderen Exponent hat... danke für deine Hilfe :)
|
|
|
|
