Kongruenz lösen < Gruppe, Ring, Körper < Algebra < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 15:37 Mo 30.12.2013 | | Autor: | DrRiese |
| Aufgabe | | Lösen Sie die Kongruenz [mm] 31x^{11} \equiv [/mm] 152 mod 156. |
Hallo,
bei dieser Kongruenz habe ich mir irgendwie die Zähne ausgebissen. Wie kriege ich z.B. die "Hoch 11" eliminiert?
Und auch mod 156 ist ja nicht gerade handlich. Aber es gilt ja [mm] \IZ_{mn} \cong \IZ_{m} \times \IZ_{n}, [/mm] wenn ggt(m,n)=1. Wegen 156= 12*13, habe ich die Gleichung umgeschrieben in
[mm] \begin{cases} 31x^{11} \equiv 152 mod 12 \\ 31x^{11} \equiv 152 mod 13 \end{cases} [/mm] = [mm] \begin{cases} 7x^{11} \equiv 8 mod 12 \\ 5x^{11} \equiv 9 mod 13 \end{cases}
[/mm]
Nun die die 5 und die 7 mit der jeweiligen Inversen multiplizieren:
(7*7 mod 12 = 1 und 8*5 mod 13 = 1)
[mm] \begin{cases} x^{11} \equiv 8 mod 12 \\ x^{11} \equiv 7 mod 13 \end{cases}
[/mm]
Nun müsste man sozusagen die Wurzel ziehen...?
Freue mich über Tipps 
LG
DrRiese
|
|
| |
|
Hallo DrRiese,
gute Vorarbeit.
> Lösen Sie die Kongruenz [mm]31x^{11} \equiv[/mm] 152 mod 156.
> Hallo,
>
> bei dieser Kongruenz habe ich mir irgendwie die Zähne
> ausgebissen. Wie kriege ich z.B. die "Hoch 11" eliminiert?
>
> Und auch mod 156 ist ja nicht gerade handlich. Aber es gilt
> ja [mm]\IZ_{mn} \cong \IZ_{m} \times \IZ_{n},[/mm] wenn ggt(m,n)=1.
> Wegen 156= 12*13, habe ich die Gleichung umgeschrieben in
>
> [mm]\begin{cases} 31x^{11} \equiv 152 mod 12 \\ 31x^{11} \equiv 152 mod 13 \end{cases}[/mm]
> = [mm]\begin{cases} 7x^{11} \equiv 8 mod 12 \\ 5x^{11} \equiv 9 mod 13 \end{cases}[/mm]
>
> Nun die die 5 und die 7 mit der jeweiligen Inversen
> multiplizieren:
>
> (7*7 mod 12 = 1 und 8*5 mod 13 = 1)
>
> [mm]\begin{cases} x^{11} \equiv 8 mod 12 \\ x^{11} \equiv 7 mod 13 \end{cases}[/mm]
>
> Nun müsste man sozusagen die Wurzel ziehen...?
>
> Freue mich über Tipps
Ja, das müsste man sozusagen. Leider ist das Ziehen von elften Wurzeln in der Praxis nicht so einfach. 
Fangen wir mal mit [mm] x^{11}\equiv 7\bmod{13} [/mm] an. x kann nicht Null sein, 13 ist prim, also gilt schonmal sicher (kleiner Fermat): [mm] x^{12}\equiv 1\bmod{13}, [/mm] also auch [mm] 7x\equiv 1\bmod{13}. [/mm] Da Du so gut im Invertieren bist, kriegst Du das sicher hin.
Ein bisschen blöder ist [mm] x^{11}\equiv 8\bmod{12}. [/mm] Auch hier ist x nicht Null, aber auch nicht teilerfremd zu 12. Offenbar muss ja x=4k gelten. Es bleiben nur [mm] x\equiv 4\bmod{12} [/mm] und [mm] x\equiv 8\bmod{12} [/mm] zu betrachten. Wenn man das ganze mal [mm] \bmod{3} [/mm] betrachtet, fällt die Entscheidung leicht, da [mm] x^{11}\equiv x\bmod{3} [/mm] ist, also [mm] x\equiv 8\bmod{3} [/mm] gelten muss. Mithin ist [mm] x\equiv 8\bmod{12}.
[/mm]
Jetzt hast Du den ganzen Bastelbogen, zum Teil sogar schon ausgeschnitten und fertig gefaltet. Du musst nur noch den Rest erledigen und komplett zusammenkleben.
Zur Ansicht ein Bild des fertigen Produkts: [mm] $\blue{x\equiv 80\bmod{156}}$.
[/mm]
Grüße
reverend
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 12:02 Mi 01.01.2014 | | Autor: | DrRiese |
Danke für die ausführliche Antwort. Hast mir sehr geholfen
LG,
DrRiese
|
|
|
|
