www.vorhilfe.de
Vorhilfe

Kostenlose Kommunikationsplattform für gegenseitige Hilfestellungen.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Forenbaum
^ Forenbaum
Status Vorhilfe
  Status Geisteswiss.
    Status Erdkunde
    Status Geschichte
    Status Jura
    Status Musik/Kunst
    Status Pädagogik
    Status Philosophie
    Status Politik/Wirtschaft
    Status Psychologie
    Status Religion
    Status Sozialwissenschaften
  Status Informatik
    Status Schule
    Status Hochschule
    Status Info-Training
    Status Wettbewerbe
    Status Praxis
    Status Internes IR
  Status Ingenieurwiss.
    Status Bauingenieurwesen
    Status Elektrotechnik
    Status Maschinenbau
    Status Materialwissenschaft
    Status Regelungstechnik
    Status Signaltheorie
    Status Sonstiges
    Status Technik
  Status Mathe
    Status Schulmathe
    Status Hochschulmathe
    Status Mathe-Vorkurse
    Status Mathe-Software
  Status Naturwiss.
    Status Astronomie
    Status Biologie
    Status Chemie
    Status Geowissenschaften
    Status Medizin
    Status Physik
    Status Sport
  Status Sonstiges / Diverses
  Status Sprachen
    Status Deutsch
    Status Englisch
    Status Französisch
    Status Griechisch
    Status Latein
    Status Russisch
    Status Spanisch
    Status Vorkurse
    Status Sonstiges (Sprachen)
  Status Neuerdings
  Status Internes VH
    Status Café VH
    Status Verbesserungen
    Status Benutzerbetreuung
    Status Plenum
    Status Datenbank-Forum
    Status Test-Forum
    Status Fragwürdige Inhalte
    Status VH e.V.

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 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
Dt. Schulen im Ausland: Mathe-Seiten:

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

kongruenzen lösen: Übung
Status: (Frage) beantwortet Status 
Datum: 14:00 Do 23.04.2015
Autor: Striker_03

Aufgabe
Bestimme das kleinste positive $x [mm] \in \IZ$ [/mm] mit

$ 54x [mm] \equiv [/mm] 1  $ mod 173

hey,
wie gehe ich solche Aufgaben ran?
Erweiterter Euklidischer Algorithmus?
Wenn ja kann man mir einer  Starthilfe geben? als Lösung soll 157 raus kommen.

MfG

        
Bezug
kongruenzen lösen: Antwort
Status: (Antwort) fertig Status 
Datum: 15:15 Do 23.04.2015
Autor: reverend

Hallo Striker,

ja, erweiterter euklidischer Algorithmus ist gut. Probiers mal aus und frag nach, wenn Du steckenbleibst.
Allerdings...

> Bestimme das kleinste positive [mm]x \in \IZ[/mm] mit
>  
> [mm]54x \equiv 1 [/mm] mod 173
>  hey,
>  wie gehe ich solche Aufgaben ran?
>  Erweiterter Euklidischer Algorithmus?
> Wenn ja kann man mir einer  Starthilfe geben? als Lösung
> soll 157 raus kommen.

...gibt es noch einen einfacheren Weg.
Zuerst musst Du natürlich sicherstellen, dass [mm] \ggT{(54,173)}=1 [/mm] ist. Das ist hier erfüllt. Außerdem ist 173 prim, da kann also eigentlich nichts schiefgehen, wenn Du mechanisch vorgehst, s.o.

Da es hier aber letztlich darum geht, das Inverse von 54 [mm] \bmod{173} [/mm] zu bestimmen, geht es eben auch noch einfacher.

Es gilt ja $54=6*9$ und [mm] 173=-1\bmod{6}. [/mm]
Sei [mm] \overline{54} [/mm] das Inverse von 54, also [mm] 54*\overline{54}\equiv 1\bmod{173}. [/mm]
Dann gilt auch [mm] 54*\overline{54}\equiv 6*9*\overline{6}*\overline{9}\bmod{173}. [/mm]

Da wir wissen, dass 173+1 durch 6 teilbar ist, ist also 174/6 das Inverse von 6. [mm] \rightarrow\quad \overline{6}\equiv 29\bmod{173} [/mm]
Andererseits ist 173+1 nicht durch 9 teilbar, aber es ist sehr leicht zu ermitteln, dass 4*173+1 durch 9 teilbar ist (überleg mal, was daran einfach ist).
Also ist (4*173+1)/9 das Inverse von 9 bzw. [mm] \overline{9}\equiv 77\bmod{173} [/mm]

Und damit bist Du ja praktisch schon am Ziel.

Probier aber unbedingt auch die "mechanische" Lösung über den erw. Euklidischen Algorithmus.

Grüße
reverend


Bezug
        
Bezug
kongruenzen lösen: Antwort
Status: (Antwort) fertig Status 
Datum: 15:58 Do 23.04.2015
Autor: Marcel

Hallo,

> Bestimme das kleinste positive [mm]x \in \IZ[/mm] mit
>  
> [mm]54x \equiv \red{1} [/mm] mod 173
>  hey,
>  wie gehe ich solche Aufgaben ran?
>  Erweiterter Euklidischer Algorithmus?
> Wenn ja kann man mir einer  Starthilfe geben? als Lösung
> soll 157 raus kommen.

es gilt folgender Satz (4.8 in "Elementare und algebraische Zahlentheorie
von Müller-Stach/Piontkowski"):

Gegeben sei die Gleichung

    $ax [mm] \equiv [/mm] b [mm] \mod [/mm] n$ mit $a,b [mm] \in \IZ$ [/mm] und $n [mm] \in \IN.$ [/mm]

Sei [mm] $d:=\ggT(a,n)$. [/mm]

  1. Falls $d [mm] \nmid [/mm] b$, dann besitzt die Gleichung keine Lösung.

  2. Sei $d [mm] \mid b\,.$ [/mm] Wähle $y,z [mm] \in \IZ$ [/mm] mit $ya+zn=d$ (etwa mit Hilfe des
  euklidischen Alg.). Dann ist obige Gleichung gleichwertig mit

    $x [mm] \equiv [/mm] y [mm] \frac{b}{d} \mod \frac{n}{d}$ [/mm] (und hat damit eine Lösung).

Das kleinste $x [mm] \in \IN$, [/mm] dass die letzte Gleichung erfüllt, bekommst Du dann
sicher selbst berechnet.

Also: Vorgehen mit diesem Satz:

  I) [mm] $\ggT(54,173)=1\,.$ [/mm] Offenbar $1 [mm] \mid b=\red{1}\,.$ [/mm] Weiter ist [mm] $a=54\,,$ $b=1\,$ [/mm] und [mm] $n=173\,.$ [/mm]

Ergebnis des [a]eukl. Algorithmus (Matlab):

    [mm] $1=(-16)*54+5*173\,,$ [/mm] also $y=-16$ (und $z=5$).

Zur obigen Kongruenz gleichwertig ist also

   $x [mm] \equiv (-16)*\frac{1}{1} \mod \frac{173}{1}$ [/mm]

Der Rest ist klar, oder?

P.S. Das Matlab-Programm läuft auch in Octave - ich empfehle allerdings,
nicht direkt Octave, sondern cygwin und dann Octave in Cygwin nachzu-
installieren (nachladen). Evtl. kannst Du den Quellcode auch anschauen
und in eine andere Programmiersprache (python?) übertragen.

Ich glaube, der Code, so, wie er dort steht, passt zu dem aus dem Buch von
Johannes Buchmann: Einführung in die Kryptographie.

Gruß,
  Marcel

Dateianhänge:
Anhang Nr. 1 (Typ: m) [nicht öffentlich]
Bezug
                
Bezug
kongruenzen lösen: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 10:46 Mo 27.04.2015
Autor: Striker_03

Hallo,

ja habe doch noch ein Problem bei der Aufgabe

ggT(173,54)

$173= 3 *54 +11$
$54 = 4*11+10$
$11= 1*10+1$
$10 = 10*1+0$

beim "rückwärts" durchgehen habe ich mein Problem:

$ 1 = 11-1*10 = 11-1*(54-4*11) = $ und nun komme ich irgendwie nicht weiter

wie kommt man am ende auf die Lösung von 157?

ps: sry marcel ich finde es ist noch nicht klar ^^ aber vielen dank für deine Antwort.

LG

Bezug
                        
Bezug
kongruenzen lösen: Antwort
Status: (Antwort) fertig Status 
Datum: 12:16 Mo 27.04.2015
Autor: ms2008de

Hallo,
> ggT(173,54)
>  
> [mm]173= 3 *54 +11[/mm]
>  [mm]54 = 4*11+10[/mm]
>  [mm]11= 1*10+1[/mm]
>  [mm]10 = 10*1+0[/mm]
>  
> beim "rückwärts" durchgehen habe ich mein Problem:
>  
> [mm]1 = 11-1*10 = 11-1*(54-4*11) =[/mm] und nun komme ich irgendwie
> nicht weiter

1=5*11 - 54
1=5*(173-3*54) -54
1= 5*173 -16*54
Da [mm] \overline{-16}=\overline{157} \in \IZ_{173} [/mm] ist,  ist [mm] \overline{157}=\overline{54}^{-1} \in \IZ_{173}. [/mm]

Viele Grüße

Bezug
                                
Bezug
kongruenzen lösen: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 12:49 Mo 27.04.2015
Autor: Striker_03

Danke, bei aufgabenteil b) ist wieder dasselbe Problem dar.

ggT(201,154)

$201=1*154+47$
$154=3*47+13$
$47=3*13+5$
$13=1*8+5$
$8=1*5+3$
$5=1*3+2$
$3= 1*2+1$
$2= 2*1+0$

dann $1 = 3-1*2 = 3-1*(5-1*3) =$ nun komme ich wieder durcheinander und weiß nicht was ich machen soll..
die 3 kann ich schreiben als $8-1*5$ usw. aber keine ahnung wie ich das umschreiben soll..
das Ergebnis ist halt $x=124$.

LG

Bezug
                                        
Bezug
kongruenzen lösen: Antwort
Status: (Antwort) fertig Status 
Datum: 13:28 Mo 27.04.2015
Autor: ms2008de

Hallo nochmal,
> ggT(201,154)
>  
> [mm]201=1*154+47[/mm]
>  [mm]154=3*47+13[/mm]
>  [mm]47=3*13+5[/mm]
>  [mm]13=1*8+5[/mm]
>  [mm]8=1*5+3[/mm]
>  [mm]5=1*3+2[/mm]
>  [mm]3= 1*2+1[/mm]
>  [mm]2= 2*1+0[/mm]
>  

Zeile 3 soll wohl heißen:
47=3*13+8

Beim rückwärts rechnen immer gucken, welche Zahl als nächstes in der Gleichung wegfällt:
1=3-2 da 2 als erstes wegfällt, ersetzen:
1=3-(5-3)
1=2*3-5, da 3 als nächstes wegfällt, ersetzen:
1=2*(8-5)-5
1=2*8 - 3*5, da 5 als nächstes wegfällt, ersetzen:
1=2*8 - 3*(13-8)
1=5*8 - 3*13, da 8 als nächstes wegfällt, ersetzen:
1=5*(47-3*13) - 3*13
1=5*47 -18*13, da 13 als nächstes wegfällt, ersetzen:
1=5*47 -18*(154-3*47)
1= 59*47 -18*154, da 47 als nächstes wegfällt, ersetzen:
1=59*(201-154) -18*154
1=59*201 - 77*154

Damit ist [mm] \overline{-77} =\overline{124}= \overline{154}^{-1} \in \IZ_{201} [/mm]

Viele Grüße

Bezug
                                        
Bezug
kongruenzen lösen: Antwort
Status: (Antwort) fertig Status 
Datum: 16:24 Mo 27.04.2015
Autor: Marcel

Hallo,

> Danke, bei aufgabenteil b) ist wieder dasselbe Problem dar.
>
> ggT(201,154)
>  
> [mm]201=1*154+47[/mm]
>  [mm]154=3*47+13[/mm]
>  [mm]47=3*13+5[/mm]
>  [mm]13=1*8+5[/mm]
>  [mm]8=1*5+3[/mm]
>  [mm]5=1*3+2[/mm]
>  [mm]3= 1*2+1[/mm]
>  [mm]2= 2*1+0[/mm]
>  
> dann [mm]1 = 3-1*2 = 3-1*(5-1*3) =[/mm] nun komme ich wieder
> durcheinander und weiß nicht was ich machen soll..
>  die 3 kann ich schreiben als [mm]8-1*5[/mm] usw. aber keine ahnung
> wie ich das umschreiben soll..
>  das Ergebnis ist halt [mm]x=124[/mm].

vielleicht interessiert Dich ja auch eine Herleitung der Formel für die Koeffizienten?

    [a]Mein Zusammenschrieb

Gruß,
  Marcel

Dateianhänge:
Anhang Nr. 1 (Typ: pdf) [nicht öffentlich]
Bezug
                        
Bezug
kongruenzen lösen: Rückfrage immmer erwünscht ;-)
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 16:17 Mo 27.04.2015
Autor: Marcel

Hallo,

> Hallo,
>  
> ja habe doch noch ein Problem bei der Aufgabe
>  
> ggT(173,54)
>  
> [mm]173= 3 *54 +11[/mm]
>  [mm]54 = 4*11+10[/mm]
>  [mm]11= 1*10+1[/mm]
>  [mm]10 = 10*1+0[/mm]
>  
> beim "rückwärts" durchgehen habe ich mein Problem:
>  
> [mm]1 = 11-1*10 = 11-1*(54-4*11) =[/mm] und nun komme ich irgendwie
> nicht weiter
>  
> wie kommt man am ende auf die Lösung von 157?
>  
> ps: sry marcel ich finde es ist noch nicht klar ^^ aber
> vielen dank für deine Antwort.

dafür brauchst Du Dich nicht zu entschuldigen - Rückfragen zeigen, dass
Du selbstständig nachdenkst. ;-)

Btw.: Ich habe ja auch den eukl. Alg. fertig programmiert zur Verfügung
gestellt, einfach, weil ich auch zu faul war, alles vorzurechnen. Ich würde
das hier genauso wie Du von Hand machen (wollen), wäre ich an Deiner
Stelle.

Gruß,
  Marcel

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


^ Seitenanfang ^
www.vorhilfe.de