www.vorhilfe.de
- Förderverein -
Der Förderverein.

Gemeinnütziger Verein zur Finanzierung des Projekts Vorhilfe.de.
Hallo Gast!einloggen | registrieren ]
Startseite · Mitglieder · Impressum
Forenbaum
^ Forenbaum
Status VH e.V.
  Status Vereinsforum

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Suchen
 Impressum
Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
Forum "Zahlentheorie" - Diophantische Gleichung
Diophantische Gleichung < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Zahlentheorie"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Diophantische Gleichung: Aufgabe
Status: (Frage) beantwortet Status 
Datum: 22:38 Sa 23.02.2008
Autor: falko43

Hallo
        
Bezug
Diophantische Gleichung: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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

Bezug
        
Bezug
Diophantische Gleichung: Antwort
Status: (Antwort) fertig Status 
Datum: 23:41 Sa 23.02.2008
Autor: MathePower

Hallo falko,

[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 []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

Bezug
                
Bezug
Diophantische Gleichung: Frage (beantwortet)
Status: (Frage) beantwortet Status 
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

Bezug
                        
Bezug
Diophantische Gleichung: Antwort
Status: (Antwort) fertig Status 
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



Bezug
                                
Bezug
Diophantische Gleichung: Frage (beantwortet)
Status: (Frage) beantwortet Status 
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!!!

Bezug
                                        
Bezug
Diophantische Gleichung: Antwort
Status: (Antwort) fertig Status 
Datum: 18:44 So 24.02.2008
Autor: MathePower

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

Bezug
        
Bezug
Diophantische Gleichung: Antwort
Status: (Antwort) fertig Status 
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

Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Zahlentheorie"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
ev.vorhilfe.de
[ Startseite | Mitglieder | Impressum ]