Kongruenzen < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 18:35 Mo 25.05.2009 | | Autor: | Lati |
| Aufgabe | Finden Sie ein [mm] x\in \IZ [/mm] mit [mm] 0\le [/mm] x< n mit folgenden Eigenschaften( Computer oder Taschenrechner sind nicht erlaubt).
a) n= 15 , x [mm] \equiv 5^{10000000000000003} [/mm] (mod 15)
b) n=125, x [mm] \equiv 2^{238476812384798234203} [/mm] (mod 125)
c) n=16, [mm] 3^x \equiv [/mm] 15 (mod 17)
d) n=2, [mm] x^{58374852} \equiv [/mm] 9 (mod 22) |
Hallo,
die Aufgabe oben sieht gar nicht so unlösbar aus, aber ich komme einfach nicht drauf wie ich hier ansetzen muss und was ich hier überhaupt verwenden soll?
zu a) Hier könnte man vielleicht den Chin. Restsatz anwenden und mod 15 ind mod 3*5 umwandeln, aber dann bin ich schnell wieder beim gleichen Problem angelangt...
zu c) hier hab ich 15 in 5*3 umgewandelt und man erhält dann die Gleichung [mm] 3^{x-1} \equiv [/mm] 5 (mod 17) und ich habe als Lösung 6 geraten aber das kann ja schlecht der Lösungsweg sein
Zu d) fällt mir noch ein dass man 9 als [mm] 3^{2} [/mm] schreiben kann und dann die Wurzel ziehen, aber dann hörts schon auf.
Vielen Dank für eure Hilfe, bin echt leicht hilflos...
Grüße
Lati
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 23:15 Mo 25.05.2009 | | Autor: | abakus |
> Finden Sie ein [mm]x\in \IZ[/mm] mit [mm]0\le[/mm] x< n mit folgenden
> Eigenschaften( Computer oder Taschenrechner sind nicht
> erlaubt).
>
> a) n= 15 , x [mm]\equiv 5^{10000000000000003}[/mm] (mod 15)
>
> b) n=125, x [mm]\equiv 2^{238476812384798234203}[/mm] (mod 125)
>
> c) n=16, [mm]3^x \equiv[/mm] 15 (mod 17)
>
> d) n=2, [mm]x^{58374852} \equiv[/mm] 9 (mod 22)
> Hallo,
>
> die Aufgabe oben sieht gar nicht so unlösbar aus, aber ich
> komme einfach nicht drauf wie ich hier ansetzen muss und
> was ich hier überhaupt verwenden soll?
Hallo,
auch den tollsten Lösungswegen sieht man hinterher nicht an, dass der geniale Mathematiker auf seine genialen Erkenntnisse durch simples Probieren gekommen ist.
Berechne also die Reste von [mm] 5^1, 5^2, 5^3 [/mm] und [mm] 5^4 [/mm] bei Teilung durch 15.
(Wenn es nicht reicht, nimm noch ein paar Werte).
Hab keine Lust, das selbst durchzurechnen; aber du wirst bezeiten auf eine Folge sich wiederholender Reste stoßen. Deine Vermutung wird dann irgendwas sein in der Art: [mm] 5^n\equiv 5^{n+k}mod [/mm] 15, und diese Vermutung beweist du dann. Daraus kannst du deine Schlussfolgerungen für den gegebenen ellenlangen Exponenten ziehen.
Gruß Abakus
>
> zu a) Hier könnte man vielleicht den Chin. Restsatz
> anwenden und mod 15 ind mod 3*5 umwandeln, aber dann bin
> ich schnell wieder beim gleichen Problem angelangt...
>
> zu c) hier hab ich 15 in 5*3 umgewandelt und man erhält
> dann die Gleichung [mm]3^{x-1} \equiv[/mm] 5 (mod 17) und ich habe
> als Lösung 6 geraten aber das kann ja schlecht der
> Lösungsweg sein
>
> Zu d) fällt mir noch ein dass man 9 als [mm]3^{2}[/mm] schreiben
> kann und dann die Wurzel ziehen, aber dann hörts schon
> auf.
>
> Vielen Dank für eure Hilfe, bin echt leicht hilflos...
>
> Grüße
>
> Lati
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 00:15 Di 26.05.2009 | | Autor: | Lati |
Hi Abakus,
danke für die Antwort!
Ok das hilft mir bei a) Hättest du mir auch noch ein paar Tipps zu den anderen Teilaufgaben?
Viele Grüße
Lati
|
|
|
| |
|
Hallo Lati,
bei (b) hilft der Satz von Euler-Fermat.
Es ist $ggT(2,125)=1$, also [mm] $2^{\varphi(125)}\equiv [/mm] 1 \ [mm] \mod [/mm] 125$
Und [mm] $\varphi(125)=\varphi\left(5^3\right)=5^3\cdot{}\left(1-\frac{1}{5}\right)=100$
[/mm]
Damit kannst du dich "hochschaukeln" ...
LG
schachuzipus
|
|
|
| |
|
> zu c) hier hab ich 15 in 5*3 umgewandelt und man erhält
> dann die Gleichung [mm]3^{x-1} \equiv[/mm] 5 (mod 17) und ich habe
> als Lösung 6 geraten aber das kann ja schlecht der
> Lösungsweg sein
Aber es ist ja [mm] 5 \equiv 3 \cdot 13 \pmod{17}[/mm], also mußt Du jetzt "nur" noch die Kongruenz [mm]3^{x-2} \equiv 13 \pmod{17}[/mm] lösen; [mm] 13 \equiv 3^4 \pmod 17}[/mm] wiederum ...
>
> Zu d) fällt mir noch ein dass man 9 als [mm]3^{2}[/mm] schreiben
> kann und dann die Wurzel ziehen, aber dann hörts schon
> auf.
Hm, soll bei d) wirklich ein [mm] x<2[/mm] bestimmt werden? Naja; jedenfalls muß das gesuchte x teilerfremd zu 22 sein. Dann kannst Du den Euler-Fermat anwenden und bekommst eine viel einfacher zu lösende Kongruenz  .
Gruß
zahlenspieler
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 16:13 Di 26.05.2009 | | Autor: | Lati |
> > zu c) hier hab ich 15 in 5*3 umgewandelt und man erhält
> > dann die Gleichung [mm]3^{x-1} \equiv[/mm] 5 (mod 17) und ich habe
> > als Lösung 6 geraten aber das kann ja schlecht der
> > Lösungsweg sein
> Aber es ist ja [mm]5 \equiv 3 \cdot 13 \pmod{17}[/mm], also mußt Du
> jetzt "nur" noch die Kongruenz [mm]3^{x-2} \equiv 13 \pmod{17}[/mm]
> lösen; [mm]13 \equiv 3^4 \pmod 17}[/mm] wiederum ...
>
> >
> > Zu d) fällt mir noch ein dass man 9 als [mm]3^{2}[/mm] schreiben
> > kann und dann die Wurzel ziehen, aber dann hörts schon
> > auf.
> Hm, soll bei d) wirklich ein [mm]x<2[/mm] bestimmt werden? Naja;
> jedenfalls muß das gesuchte x teilerfremd zu 22 sein. Dann
> kannst Du den Euler-Fermat anwenden und bekommst eine viel
> einfacher zu lösende Kongruenz .
Hi Zahlenspieler,
danke für die Hilfe!
Nein bei d) soll ein x<22 bestimmt werden. Könntest du vll nochmal etwas genauer erklären was du damit meinst hier den Euler-Fermat anweden zu können?
Ich mein, wenn du sagst dass x und 22 teilerfremd sein müssen,gibt es ja immer noch die Möglichkeiten 3,5,7,9,13,15,17,19,21
Ich habe zusätzlich mal noch phi(22) berechnet: phi soll die Eulerfunktion darstellen(find grad das Zeichen nicht):
phi(22)=22*(1-1/2)(1-1/11)=10
Hieraus müsste doch folgen, dass [mm] x^{10} \equiv [/mm] 1 (mod 22) sein muss oder?
Dann könnte man [mm] x^{29187426} [/mm] schreiben als [mm] x^{29187420}*x^{6} [/mm] und dann [mm] (x^{10})^{2918742} [/mm] * [mm] x^{6} [/mm] würde übrig bleiben:
[mm] x^{6} \equiv [/mm] 3 (mod 22)
Ich seh gerade, dass es viel besser ist wenn ich am Anfang nicht die Wurzel ziehe.
Dann komme ich auf [mm] x^{58374852}= x^{58374850}*x^2= (x^{10})^{5837485} *x^2
[/mm]
Bleibt zu lösen:
[mm] x^2 \equiv [/mm] 9 (mod 22)
Und das müsste x=3 als Lösung haben.
Meintest du das so?Und kann ich das so machen?
Viele Grüße
Lati
> Gruß
> zahlenspieler
|
|
|
| |
|
Hallo Lati,
> > > zu c) hier hab ich 15 in 5*3 umgewandelt und man erhält
> > > dann die Gleichung [mm]3^{x-1} \equiv[/mm] 5 (mod 17) und ich habe
> > > als Lösung 6 geraten aber das kann ja schlecht der
> > > Lösungsweg sein
> > Aber es ist ja [mm]5 \equiv 3 \cdot 13 \pmod{17}[/mm], also mußt
> Du
> > jetzt "nur" noch die Kongruenz [mm]3^{x-2} \equiv 13 \pmod{17}[/mm]
> > lösen; [mm]13 \equiv 3^4 [mm]x \equiv 3 [/mm] (mod 22)\pmod 17}[/mm] wiederum ...
> >
> > >
> > > Zu d) fällt mir noch ein dass man 9 als [mm]3^{2}[/mm] schreiben
> > > kann und dann die Wurzel ziehen, aber dann hörts schon
> > > auf.
> > Hm, soll bei d) wirklich ein [mm]x<2[/mm] bestimmt werden? Naja;
> > jedenfalls muß das gesuchte x teilerfremd zu 22 sein. Dann
> > kannst Du den Euler-Fermat anwenden und bekommst eine viel
> > einfacher zu lösende Kongruenz .
>
> Hi Zahlenspieler,
>
> danke für die Hilfe!
> Nein bei d) soll ein x<22 bestimmt werden. Könntest du vll
> nochmal etwas genauer erklären was du damit meinst hier den
> Euler-Fermat anweden zu können?
> Ich mein, wenn du sagst dass x und 22 teilerfremd sein
> müssen,gibt es ja immer noch die Möglichkeiten
> 3,5,7,9,13,15,17,19,21
>
> Ich habe zusätzlich mal noch phi(22) berechnet: phi soll
> die Eulerfunktion darstellen(find grad das Zeichen nicht):
> phi(22)=22*(1-1/2)(1-1/11)=10
>
> Hieraus müsste doch folgen, dass [mm]x^{10} \equiv[/mm] 1 (mod 22)
> sein muss oder?
Ja, siehe den ![[]](/images/popup.gif) Satz von Fermat-Euler.
>
> Dann könnte man [mm]x^{29187426}[/mm] schreiben als
> [mm]x^{29187420}*x^{6}[/mm] und dann [mm](x^{10})^{2918742}[/mm] * [mm]x^{6}[/mm]
> würde übrig bleiben:
>
> [mm]x^{6} \equiv[/mm] 3 (mod 22)
>
> Ich seh gerade, dass es viel besser ist wenn ich am Anfang
> nicht die Wurzel ziehe.
> Dann komme ich auf [mm]x^{58374852}= x^{58374850}*x^2= (x^{10})^{5837485} *x^2[/mm]
>
> Bleibt zu lösen:
>
> [mm]x^2 \equiv[/mm] 9 (mod 22)
>
> Und das müsste x=3 als Lösung haben.
>
> Meintest du das so?Und kann ich das so machen?
>
Ja, das kannst Du so machen.
Die Kongruenz
[mm]x^2 \equiv[/mm] 9 (mod 22)
hat noch eine zweite Lösung.
Aus [mm]x^{2}=9[/mm] folgt nämlich [mm]x=3 \vee x=-3[/mm]
Übertragen auf diese Aufgabe sind dann
[mm]x \equiv 3 [/mm] (mod 22)
und
[mm]x \equiv -3 \equiv 19[/mm] (mod 22)
Lösungen.
>
> Viele Grüße
>
> Lati
>
> > Gruß
> > zahlenspieler
>
Gruß
MathePower
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 21:16 Di 26.05.2009 | | Autor: | Lati |
Hallo zusammen,
vielen Dank nochmal für eure Hilfe!
Viele Grüße
Lati
|
|
|
|
