Satz von Euler-Fermat anwenden < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Sei n=545 und m=667 und a [mm] \in \IZ. [/mm]
Löse die Gleichung [mm] a^9 \equiv [/mm] 545 (mod 667) mit dem Satz von Euler-Fermat. |
Hallo Zusammen,
Meine Idee bisher: Mit phi(m)=616 gilt nach dem Satz von Euler-Fermat:
545^(616) [mm] \equiv [/mm] 1 (mod 667) also dann auch [mm] (a^9)^{616} \equiv [/mm] 545^616 [mm] \equiv [/mm] 1 (mod 667)
Wie kann ich nun diese Gleichung weiter lösen? Denn ist ja jetzt quasi nur noch
[mm] (a^9)^{616} \equiv [/mm] 1 (mod 667) zu lösen, oder?
Über einen Tipp wäre ich dankbar. Lieben Gruß
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 22:26 Do 13.07.2017 | | Autor: | felixf |
Moin!
> Sei n=545 und m=667 und a [mm]\in \IZ.[/mm]
> Löse die Gleichung [mm]a^9 \equiv[/mm]
> 545 (mod 667) mit dem Satz von Euler-Fermat.
>
> Hallo Zusammen,
> Meine Idee bisher: Mit phi(m)=616 gilt nach dem Satz von
> Euler-Fermat:
>
> [mm] 545^{616}[/mm] [mm]\equiv[/mm] 1 (mod 667) also dann auch [mm](a^9)^{616} \equiv[/mm]
> [mm] 545^{616}[/mm] [mm]\equiv[/mm] 1 (mod 667)
Ja, aber das hilft dir nicht direkt weiter.
> Wie kann ich nun diese Gleichung weiter lösen? Denn ist ja
> jetzt quasi nur noch
> [mm](a^9)^{616} \equiv[/mm] 1 (mod 667) zu lösen, oder?
Nun, die Gleichung wird von jedem $a$, welches teilerfremd zu 667 ist, erfüllt. Hilft dir also nicht weiter 
Versuch doch mal folgendes: 9 und 616 sind teilerfremd. Also kannst du $1 = x [mm] \cdot [/mm] 9 + y [mm] \cdot [/mm] 616$ schreiben.
Jetzt kombiniere das doch mal mit [mm] $a^9 \equiv [/mm] 545 [mm] \pmod{667}$ [/mm] und [mm] $a^{616} \equiv [/mm] 1 [mm] \pmod{667}$.
[/mm]
LG Felix
|
|
|
| |
|
Hallo Felix,
deine Antwort hat mir schon weiter geholfen, vielen Dank dafür.
[mm] a^9 \equiv [/mm] 545 (mod 667)
a^616 [mm] \equiv [/mm] 1 (mod 667)
ggT(616,9)=1=(-2)*616+137*9 mit x=-2 und y=137
Ich potenziere die erste Gleichung mit 137 und die zweite mit -2 und erhalte
a^(9*137) [mm] \equiv [/mm] 545^137 (mod 667)
a^(-2)*616 [mm] \equiv [/mm] 1^(-2) [mm] \equiv [/mm] 1 (mod 667)
Diese beiden multipliziere ich mit den Rechenregeln für Kongruenzen und erhalte dann die Gleichung
a^ ((-2)*616+9*137) [mm] \equiv [/mm] 1*545^137 (mod 667)
[mm] a^1 \equiv [/mm] a [mm] \equiv [/mm] 545^137 (mod 667)
Und müsste nun die Gleichung a [mm] \equiv [/mm] 545^137 (mod 667) lösen.
ich habe das Ganze mit square-and-multiply über die Binärstellung gelöst und erhalte a=397.
Das Ergebnis ist richtig. Danke!
LG
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 13:20 So 16.07.2017 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
