Diophantische Gleichung < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 22:38 Sa 23.02.2008 | | Autor: | falko43 |
Hallo
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 23:16 Sa 23.02.2008 | | Autor: | BuRn88 |
Also: Das Problem ist, dass es in dem Beispiel keine ganzzahlige Lösung gibt.
Und da es bei diophantische Gleichungen gerade um die Findung ganzzahliger Lösungen geht.. naja ;)
3X = 4 besitzt keine Lösung, da bei diophantischen Gleichungen nur ganzzahlige Lösungen gesucht sind. (von wiki)
lG
|
|
|
| |
|
Hallo falko,
![[willkommenmr]](/images/smileys/willkommenmr.png "[willkommenmr]")
> Hallo zusammen! Ich muss folgende Aufgabe lösen:
>
> 229 * x [mm]\equiv[/mm] 367 (mod 482)
> Nochmal in Worten Welches Vielfache von 229 ergibt geteilt
> durch 482 den Rest 367?
Ja.
>
> Kann mir jemand helfen? Bitte plus Rechenweg!!!
Die Lösung des Problems erfolgt mit Hilfe der ![[]](/images/popup.gif) Eulerschen [mm]\varphi[/mm]-Funktion
Zerlege zunächst einmal die Zahl 482 in ihre Primfaktoren:
[mm]482=p_{1}*p_{2} * \ \dots \ * p_{r}[/mm]
Die Lösung obiger Gleichung ergibt sich zu: [mm]x=229^{\varphi\left(482\right)-1}*367[/mm], denn es gilt [mm]229^{\varphi\left(482\right)}\equiv1 (mod 482)[/mm]
Nun [mm]229^{\varphi\left(482\right)-1}[/mm] rechnet man so nicht aus.
Statt dessen berechne lieber
[mm]229^{1}\equiv 229 (mod 482)[/mm]
[mm]229^{2}\equiv r_{1} (mod 482)[/mm]
[mm]229^{4}\equiv r_{1}*r_{1} \equiv r_{2} (mod 482)[/mm]
[mm]\dots[/mm]
Berechne also aller 2er-Potenzen von 229, für die [mm]2^{k} \le \varphi\left(482\right)-1[/mm]
Stelle dann [mm]\varphi\left(482\right)-1[/mm] als Summe von 2er-Potenzen dar:
Dann ist [mm]{\varphi\left(482\right)-1}=2^{k_{1}}+ \ \dots \ +2^{k_{n}}[/mm]
Demnach gilt dann: [mm]229^{\varphi\left(482\right)-1}=229^{2^{k_{1}}}* \ \dots \ * 229^{2^{k_{n}}}[/mm]
Berechne dies und multipliziere es mit 367 und ermittle den Rest bei Division durch 482. Das ist dann das gesuchte x.
> Thanxxx
>
> Ich habe diese Frage in keinem Forum auf anderen
> Internetseiten gestellt.
Gruß
MathePower
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 09:31 So 24.02.2008 | | Autor: | falko43 |
Danke für die schnelle Antwort. Leider hänge ich jetzt im letzten Schritt, weil meine Zahlen so groß sind.
[mm] {\varphi\left(482\right)-1}=302 [/mm] (wenn ich richtig gerechnet habe)
Wie kann ich denn jetzt weiter rechnen?
Sorry, bin Zahlentheorie-Anfänger!
Viele Grüße
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 10:02 So 24.02.2008 | | Autor: | DaMazen |
Moin, ich habe bei $ [mm] {\varphi\left(482\right)-1}=239 [/mm] $ raus...
Gesucht sind die Primen Restklassen, kennst du die Formel?
Man Zerlegt 482 mit der PFZ:
482 = 2*241
also ergibt sich für die Primen Restklassen [mm] 241(1-\bruch{1}{241})*2(1-\bruch{1}{2}) [/mm] = 240
Vielleicht klappt es damit besser.
Wenn du die Zahlen durchgehst, kannst du auch mit der Information:
z.B.:
[mm] 229^2 \equiv [/mm] 385 (482)
daraus folgt ebenso:
[mm] 229^239\equiv [/mm] 229^(2*119+1) [mm] \equiv [/mm] 385^119 * [mm] 385^1
[/mm]
Vielleicht kommst du damit weiter, sonst einfach nochmal fragen
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 10:28 So 24.02.2008 | | Autor: | falko43 |
Ja, der morgen ist eindeutig zu früh:
Ich hatte bei [mm] {\varphi\left(482\right)-1} [/mm] auch 239 raus und meinte
[mm] 229^{239}\equiv302 [/mm] (mod 482)
Wie komme ich jetzt zu meinem x???
Nochmals vielen Dank!!!
|
|
|
| |
|
Hallo falko,
> Ja, der morgen ist eindeutig zu früh:
>
> Ich hatte bei [mm]{\varphi\left(482\right)-1}[/mm] auch 239 raus und
> meinte
>
> [mm]229^{239}\equiv302[/mm] (mod 482)
das musst Du nochmal nachrechnen.
>
> Wie komme ich jetzt zu meinem x???
[mm]x \equiv 229^{239}*367 (mod 482)[/mm]
>
> Nochmals vielen Dank!!!
Gruß
MathePower
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 10:01 So 24.02.2008 | | Autor: | Manatu |
Hallo Falko,
es gibt auch noch eine andere Möglichkeit, deine Aufgabe zu lösen. Ich weiß nicht, welches Hintergrundwissen du schon hast. Wenn du den (erweiterten) Euklidischen Algorithmus kennst, kannst du auch schlicht mit diesem das Inverse von 229 modulo 482 berechnen. Sagen wir, das Inverse von 229 modulo 482 heißt $u$, dann gilt nämlich dann:
[mm] $x\equiv 367\cdot [/mm] u [mm] \quad (mod\, [/mm] 482)$.
Das heißt, du müsstest danach lediglich das Produkt von 367 und u modulo 482 berechnen.
Vielleicht ist dieser Weg mehr Rechenaufwand, aber ich meine, er ist sehr simpel und gut praktikabel, weil es für den euklidischen Algorithmus ein wunderbar einfaches, tabellarisches Schema gibt. Außerdem hat man den angenehmen nebeneffekt, dass man zugleich auch die Antwort auf die Frage bekommt, ob es überhaupt eine Lösung gibt.
Wenn du den Euklidischen Algorithmus nicht kennst, aber Interesse hast, poste ich dir hier beispielhaft, wie er anzuwenden ist.
Gruß, Manatu
|
|
|
|
