Potenz Kongruenz lösen < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 21:36 So 09.12.2012 | | Autor: | icarus89 |
| Aufgabe | Lösen Sie folgende Kongruenz:
[mm] x^{54} \equiv [/mm] 38 mod 143 |
Hallo!
Ich hab keinen blassen Schimmer, wie man sowas ohne Tabellenkalkulation oder ohne sich die Hände wund zu rechnen lösen soll. Hab nach sowas gegoogelt, aber nur was dazu gefunden, wenn der Modul ne Primzahl ist, es also Primitivwurzeln gibt, die es hier ja nicht gibt.
Wir hatten auch nen anderes Beispiel: [mm] x^{555} \equiv [/mm] 10 mod 11, dass man aber vereinfachen konnte über den Satz von Euler zu [mm] x^{5} \equiv [/mm] 10 mod 11, sodass man dann einfach alles ausrechnen konnte, weil die Zahlen ja nicht mehr so groß waren und es auch nicht so viel einzusetzen gibt. Aber den Trick kann man hier ja nicht anwenden, da [mm] \varphi(143)=120>54
[/mm]
Wie kann man das dann hier lösen?
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 21:38 So 09.12.2012 | | Autor: | abakus |
> Lösen Sie folgende Kongruenz:
> [mm]x^{54} \equiv[/mm] 38 mod 143
> Hallo!
> Ich hab keinen blassen Schimmer, wie man sowas ohne
> Tabellenkalkulation oder ohne sich die Hände wund zu
> rechnen lösen soll. Hab nach sowas gegoogelt, aber nur was
> dazu gefunden, wenn der Modul ne Primzahl ist, es also
> Primitivwurzeln gibt, die es hier ja nicht gibt.
> Wir hatten auch nen anderes Beispiel: [mm]x^{555} \equiv[/mm] 10 mod
> 11, dass man aber vereinfachen konnte über den Satz von
> Euler zu [mm]x^{5} \equiv[/mm] 10 mod 11, sodass man dann einfach
> alles ausrechnen konnte, weil die Zahlen ja nicht mehr so
> groß waren und es auch nicht so viel einzusetzen gibt.
> Aber den Trick kann man hier ja nicht anwenden, da
> [mm]\varphi(143)=120>54[/mm]
> Wie kann man das dann hier lösen?
Hallo,
143=11*13.
Gruß Abakus
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 21:56 So 09.12.2012 | | Autor: | icarus89 |
> Hallo,
> 143=11*13.
> Gruß Abakus
>
Also [mm] x^{54} \equvi [/mm] 5 mod 11
und [mm] x^{54} \equiv [/mm] 12 mod 13
lösen?
Das hab ich auch schon ausprobiiert...
Das vereinfacht sich über Euler, dann kommt man auf nen paar Lösungen mod 11 und mod 13, die man über den Chinesischen Restsatz zu einer Lösung mod 143 kombinieren kann. Diese Lösungen entsprechen aber nicht den tatsächlichen Lösungen von dieser Kongruenz...
|
|
|
| |
|
Wie kommt man auf die Umformungen
[mm] x^{54} \equiv [/mm] 5 mod 11
[mm] x^{54} \equiv [/mm] 12 mod 13
Die Module sind klar, sie stammen aus den Primfaktoren von 143. Aber wie kommt man auf 5 und 12?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 08:10 Do 13.07.2017 | | Autor: | abakus |
> Wie kommt man auf die Umformungen
>
> [mm]x^{54} \equiv[/mm] 5 mod 11
>
> [mm]x^{54} \equiv[/mm] 12 mod 13
>
> Die Module sind klar, sie stammen aus den Primfaktoren von
> 143. Aber wie kommt man auf 5 und 12?
Wir haben
[mm]x^{54} \equiv[/mm] 38 mod 11
und
[mm]x^{54} \equiv[/mm] 38 mod 13.
Nun gilt ja
[mm]38 \equiv[/mm] 5 mod 11
und
[mm]38 \equiv[/mm] 12 mod 13.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 22:24 So 09.12.2012 | | Autor: | felixf |
Moin!
> > Hallo,
> > 143=11*13.
> > Gruß Abakus
> >
>
> Also [mm]x^{54} \equvi[/mm] 5 mod 11
> und [mm]x^{54} \equiv[/mm] 12 mod 13
> lösen?
Genau.
> Das hab ich auch schon ausprobiiert...
> Das vereinfacht sich über Euler, dann kommt man auf nen
> paar Lösungen mod 11 und mod 13, die man über den
> Chinesischen Restsatz zu einer Lösung mod 143 kombinieren
> kann.
Genau.
> Diese Lösungen entsprechen aber nicht den
> tatsächlichen Lösungen von dieser Kongruenz...
In dem Fall hast du dich wohl irgendwo verrechnet. Ohne deine Rechnungen sehen zu koennen kann man da nicht viel mehr zu sagen...
LG Felix
|
|
|
|
