matheraum.de
Raum für Mathematik
Offene Informations- und Nachhilfegemeinschaft

Für Schüler, Studenten, Lehrer, Mathematik-Interessierte.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Forenbaum
^ Forenbaum
Status Mathe
  Status Schulmathe
    Status Primarstufe
    Status Mathe Klassen 5-7
    Status Mathe Klassen 8-10
    Status Oberstufenmathe
    Status Mathe-Wettbewerbe
    Status Sonstiges
  Status Hochschulmathe
    Status Uni-Analysis
    Status Uni-Lin. Algebra
    Status Algebra+Zahlentheo.
    Status Diskrete Mathematik
    Status Fachdidaktik
    Status Finanz+Versicherung
    Status Logik+Mengenlehre
    Status Numerik
    Status Uni-Stochastik
    Status Topologie+Geometrie
    Status Uni-Sonstiges
  Status Mathe-Vorkurse
    Status Organisatorisches
    Status Schule
    Status Universität
  Status Mathe-Software
    Status Derive
    Status DynaGeo
    Status FunkyPlot
    Status GeoGebra
    Status LaTeX
    Status Maple
    Status MathCad
    Status Mathematica
    Status Matlab
    Status Maxima
    Status MuPad
    Status Taschenrechner

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:Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
StartseiteMatheForenZahlentheorieKongruenzen
Foren für weitere Studienfächer findest Du auf www.vorhilfe.de z.B. Astronomie • Medizin • Elektrotechnik • Maschinenbau • Bauingenieurwesen • Jura • Psychologie • Geowissenschaften
Forum "Zahlentheorie" - Kongruenzen
Kongruenzen < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Zahlentheorie"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Kongruenzen: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 19:05 Di 22.09.2009
Autor: D-C

Aufgabe
a)
6x [mm] \equiv [/mm] 1 mod 11

Lösbar, wenn ja warum?
Wenn ja, Lösung bestimmen.

b)
Bestimmen Sie alle Lösungen der Kongruenz
[mm] x^2 \equiv [/mm] 8 mod 77.

Zu a)

ax = b(m) ist  ja genau dann lösbar, wenn ggT(a,m) teilt b.

Also:

6x [mm] \equiv [/mm] 1(11)
ggT(6,11)
11 = 1*6 + 5
  6 = 1*5 + 1
  5 = 5*1 + 0

=> ggT(6,11) = 1
1 teilt 1
=> ist eindeutig lösbar


Als Lösung soll herauskommen x [mm] \equiv [/mm] 2(11) .

Nur wie kommt man darauf?


zu b)

Wie geht man hier am besten vor?


Gruß

D-C

        
Bezug
Kongruenzen: Antwort
Status: (Antwort) fertig Status 
Datum: 19:17 Di 22.09.2009
Autor: MathePower

Hallo D-C,

> a)
>  6x [mm]\equiv[/mm] 1 mod 11
>  
> Lösbar, wenn ja warum?
>  Wenn ja, Lösung bestimmen.
>  
> b)
>  Bestimmen Sie alle Lösungen der Kongruenz
>  [mm]x^2 \equiv[/mm] 8 mod 77.
>  Zu a)
>  
> ax = b(m) ist  ja genau dann lösbar, wenn ggT(a,m) teilt
> b.
>  
> Also:
>  
> 6x [mm]\equiv[/mm] 1(11)
>  ggT(6,11)
>  11 = 1*6 + 5
>    6 = 1*5 + 1
>    5 = 5*1 + 0
>  
> => ggT(6,11) = 1
>  1 teilt 1
>  => ist eindeutig lösbar

>  
>
> Als Lösung soll herauskommen x [mm]\equiv[/mm] 2(11) .


Wende den euklidischen Algorithmus rückwärts an:

[mm]1=1 \* 6 - 1 \* 5[/mm]

Ersetze nun die 5 aus

[mm]11=1 \* 6 +5[/mm]

Damit erigibt sich

[mm]1=1 \* 6 - 1 \* \left(1 \* 11 - 1 \* 6\right)=2 \* 6 - 1\* 11[/mm]

Somit ist 2 das Inverse von 6 modulo 11.


>  
> Nur wie kommt man darauf?
>  
>
> zu b)
>  
> Wie geht man hier am besten vor?
>  
>
> Gruß
>  
> D-C


Gruss
MathePower

Bezug
                
Bezug
Kongruenzen: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 22:37 Di 22.09.2009
Autor: D-C

Stimmt da war ja noch die Möglichkeit, das Rückwärts anzuwenden, da hätte ich auch drauf kommen können, aber na ja manchmal sieht mans irgendwie einfach nicht... : )

Gruß

D-C

Bezug
                
Bezug
Kongruenzen: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 16:56 Mi 23.09.2009
Autor: D-C


> Wende den euklidischen Algorithmus rückwärts an:
>  
> [mm]1=1 \* 6 - 1 \* 5[/mm]
>  
> Ersetze nun die 5 aus
>  
> [mm]11=1 \* 6 +5[/mm]
>  
> Damit erigibt sich
>  
> [mm]1=1 \* 6 - 1 \* \left(1 \* 11 - 1 \* 6\right)=2 \* 6 - 1\* 11[/mm]
>  
> Somit ist 2 das Inverse von 6 modulo 11.
>  

So, hab das nochmal für mich gerechnet und bin nun auch auf das Ergebnis gekommen.

Aber bei einer anderen Aufgabe scheine ich noch nen Fehler zu machen:

12x [mm] \equiv [/mm] 5 mod 17

ggT(12,17)
17 = 1*12 + 5
12 = 2*5 + 2
  5 = 2*2 + 1
  2 = 2*1 + 0

ggT(12,17) = 1 , 1 teilt 5 => eindeutig lösbar

Rückwärts:
1 =1*5 - 2*2
   Ersetzen der 2
   =1*5 - 2*(1*12 - 2*5)
   =1*5 -  2*12 + 4*5
   =5*5 - 2*12
   Ersetzen der 5
   =5*(1*17-1*12) - 2*12
   =5*17 - 5*12 - 2*12
   =5*17-7*12

Herauskommen soll  x [mm] \equiv [/mm] 16 mod 17 ...




Und wie wäre es bei 3x [mm] \equiv [/mm] 19 mod 31

ggT(3,31)
31 = 10*3 + 1
3 = 3*1 + 0

Hier besteht der Rückwärtsschritt ja nur aus
1 = 1*31 - 10*3

Ersetzen kann ich hier ja dann nichts weiter..

Gruß
D-C

Bezug
                        
Bezug
Kongruenzen: Antwort
Status: (Antwort) fertig Status 
Datum: 17:19 Mi 23.09.2009
Autor: MathePower

Hallo D-C.

> > Wende den euklidischen Algorithmus rückwärts an:
>  >  
> > [mm]1=1 \* 6 - 1 \* 5[/mm]
>  >  
> > Ersetze nun die 5 aus
>  >  
> > [mm]11=1 \* 6 +5[/mm]
>  >  
> > Damit erigibt sich
>  >  
> > [mm]1=1 \* 6 - 1 \* \left(1 \* 11 - 1 \* 6\right)=2 \* 6 - 1\* 11[/mm]
>  
> >  

> > Somit ist 2 das Inverse von 6 modulo 11.
>  >  
>
> So, hab das nochmal für mich gerechnet und bin nun auch
> auf das Ergebnis gekommen.
>  
> Aber bei einer anderen Aufgabe scheine ich noch nen Fehler
> zu machen:
>  
> 12x [mm]\equiv[/mm] 5 mod 17
>  
> ggT(12,17)
>  17 = 1*12 + 5
>  12 = 2*5 + 2
>    5 = 2*2 + 1
>    2 = 2*1 + 0
>  
> ggT(12,17) = 1 , 1 teilt 5 => eindeutig lösbar
>  
> Rückwärts:
>  1 =1*5 - 2*2
>     Ersetzen der 2
>     =1*5 - 2*(1*12 - 2*5)
>     =1*5 -  2*12 + 4*5
>     =5*5 - 2*12
>     Ersetzen der 5
>     =5*(1*17-1*12) - 2*12
>     =5*17 - 5*12 - 2*12
>     =5*17-7*12


[ok]


>  
> Herauskommen soll  x [mm]\equiv[/mm] 16 mod 17 ...
>  
>


Es ist [mm]-7 \equiv 10[/mm] das Inverse von 12 modulo 17.

Daher ergibt sich [mm]x \equiv 5*12^{-1} = 5*10 =50 \equiv 16[/mm] modulo 17.


>
>
> Und wie wäre es bei 3x [mm]\equiv[/mm] 19 mod 31
>  
> ggT(3,31)
>  31 = 10*3 + 1
>  3 = 3*1 + 0
>  
> Hier besteht der Rückwärtsschritt ja nur aus
> 1 = 1*31 - 10*3


Hier ist [mm]-10 \equiv 21[/mm] das Inverse von 3 modulo 31.

Damit ergibt sich [mm]x \equiv 19*3^{-1}=19*21 \equiv 27[/mm] modulo 31.


>
> Ersetzen kann ich hier ja dann nichts weiter..
>  
> Gruß
>  D-C


Gruss
MathePower

Bezug
                                
Bezug
Kongruenzen: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 18:00 Mi 23.09.2009
Autor: D-C

>5*17-7*12
>
> [ok]
>  
> Es ist [mm]-7 \equiv 10[/mm] das Inverse von 12 modulo 17.


Soweit klar.

> Daher ergibt sich [mm]x \equiv 5*12^{-1} = 5*10 =50 \equiv 16[/mm]
> modulo 17.

Die Zeile ist mir auch klar, bis auf die 5, bzw. unten die 19 !?
  

> > 1 = 1*31 - 10*3
>
>
> Hier ist [mm]-10 \equiv 21[/mm] das Inverse von 3 modulo 31.
>  
> Damit ergibt sich [mm]x \equiv 19*3^{-1}=19*21 \equiv 27[/mm] modulo
> 31.

Gruß´

D-C

Bezug
                                        
Bezug
Kongruenzen: Antwort
Status: (Antwort) fertig Status 
Datum: 18:41 Mi 23.09.2009
Autor: MathePower

Hallo D-C,

> >5*17-7*12
>  >

> > [ok]
>  >  
> > Es ist [mm]-7 \equiv 10[/mm] das Inverse von 12 modulo 17.
>  
>
> Soweit klar.
>  
> > Daher ergibt sich [mm]x \equiv 5*12^{-1} = 5*10 =50 \equiv 16[/mm]
> > modulo 17.
>  
> Die Zeile ist mir auch klar, bis auf die 5, bzw. unten die
> 19 !?


Wir haben die Kongruenz

[mm]12*x \equiv 5 \ \left(17\right)[/mm]

zu lösen.

Multplizieren wir obige Gleichung mit dem Inversen von 12,
dann ergibt sich:

[mm]\blue{12^{-1}}*12*x \equiv \blue{12^{-1}}*5[/mm]

[mm]1*x \equiv \blue{12^{-1}}*5[/mm]

Da die Multiplikation kommutativ ist, gilt:

[mm]x \equiv \blue{12^{-1}}*5= 5*\blue{12^{-1}}[/mm]

Analog für die zweite Aufgabe.


>    
>
> > > 1 = 1*31 - 10*3
> >
> >
> > Hier ist [mm]-10 \equiv 21[/mm] das Inverse von 3 modulo 31.
>  >  
> > Damit ergibt sich [mm]x \equiv 19*3^{-1}=19*21 \equiv 27[/mm] modulo
> > 31.
>  
> Gruß´
>  
> D-C


Gruss
MathePower

Bezug
                                                
Bezug
Kongruenzen: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 19:09 Mi 23.09.2009
Autor: D-C


> Analog für die zweite Aufgabe.
>  


Habs mal ausführlich durchgerechnet:

1 = 1*31 - 10*3

Es ist -10 [mm] \equiv [/mm] 21 das Inverse von 19 mod 31

Daraus folgt für 3x [mm] \equiv [/mm] 19 mod 31:

[mm] 3^{-1} [/mm] * 3x [mm] \equiv 3^{-1} [/mm] *19

1x [mm] \equiv 3^{-1} [/mm] *19
  x [mm] \equiv [/mm] 19 * [mm] 3^{-1} [/mm]
  x [mm] \equiv [/mm] 19 *21
  x [mm] \equiv [/mm] 399
  x [mm] \equiv [/mm] 27 mod 31

Das sollte dann jetzt so richtig sein hoffe ich !? : )


Gruß

D-C

Bezug
                                                        
Bezug
Kongruenzen: Antwort
Status: (Antwort) fertig Status 
Datum: 19:17 Mi 23.09.2009
Autor: MathePower

Hallo D-C,


> > Analog für die zweite Aufgabe.
>  >  
>
>
> Habs mal ausführlich durchgerechnet:
>  
> 1 = 1*31 - 10*3
>  
> Es ist -10 [mm]\equiv[/mm] 21 das Inverse von 19 mod 31
>  
> Daraus folgt für 3x [mm]\equiv[/mm] 19 mod 31:
>  
> [mm]3^{-1}[/mm] * 3x [mm]\equiv 3^{-1}[/mm] *19
>  
> 1x [mm]\equiv 3^{-1}[/mm] *19
>    x [mm]\equiv[/mm] 19 * [mm]3^{-1}[/mm]
>    x [mm]\equiv[/mm] 19 *21
>    x [mm]\equiv[/mm] 399
>    x [mm]\equiv[/mm] 27 mod 31
>  
> Das sollte dann jetzt so richtig sein hoffe ich !? : )
>  


Ja. [ok]


>
> Gruß
>  
> D-C


Gruss
MathePower

Bezug
                                                                
Bezug
Kongruenzen: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 19:24 Mi 23.09.2009
Autor: D-C

Hi.

Schön,
dann danke für die ausführliche Hilfe : )

Gruß

D-C

Bezug
        
Bezug
Kongruenzen: Antwort
Status: (Antwort) fertig Status 
Datum: 19:33 Di 22.09.2009
Autor: abakus


> a)
>  6x [mm]\equiv[/mm] 1 mod 11
>  
> Lösbar, wenn ja warum?
>  Wenn ja, Lösung bestimmen.
>  
> b)
>  Bestimmen Sie alle Lösungen der Kongruenz
>  [mm]x^2 \equiv[/mm] 8 mod 77.
>  Zu a)
>  
> ax = b(m) ist  ja genau dann lösbar, wenn ggT(a,m) teilt
> b.
>  
> Also:
>  
> 6x [mm]\equiv[/mm] 1(11)
>  ggT(6,11)
>  11 = 1*6 + 5
>    6 = 1*5 + 1
>    5 = 5*1 + 0
>  
> => ggT(6,11) = 1
>  1 teilt 1
>  => ist eindeutig lösbar

>  
>
> Als Lösung soll herauskommen x [mm]\equiv[/mm] 2(11) .
>  
> Nur wie kommt man darauf?

Mit einem endlichen Aufwand des Probierens von Möglichkeiten.
Vermutlich werden die Terme 6*1, 6*2, 6*3, ... 6*11 allesamt  verschiedene Reste mod 11 liefern.
Da es nur 11 mögliche Reste gibt, hast du spätestens im 11. Versuch auch den gewünschten Rest 2.
Wenn man natürlich "sieht", dass 1 [mm] \equiv [/mm] 12 mod 11 ist und 12 durch 6 teilbar ist, kann man aus 6x [mm] \equiv [/mm] 1 mod 11 sofort auf 6x [mm] \equiv [/mm] 12 mod 11 und damit auf die Lösung schließen.

>  
>
> zu b)
>  
> Wie geht man hier am besten vor?

Spätestens im 77. Versuch hast du die Lösung.
Da allerdings 76 [mm] \equiv [/mm] -1 mod 77, 75 [mm] \equiv [/mm] -2 mod 77 usw gilt, ist [mm] 76^2 \equiv 1^2 [/mm] mod 77,  [mm] 75^2 \equiv 2^2 [/mm] mod 77 usw.
Die Reste treten also paarweise auf, sodass du nur die Hälfte aller 77 Möglichkeiten testen musst.
Alternative: Addiere zu 8  so lange die Zahl 77, bis du eine Quadratzahl erhältst.
2. Alternative:
Eine Zahl, die bei Teilung durch 77 den Rest 8 lässt, lässt bei Teilung durch 7 den Rest 1 und bei ilung durch 11 den Rest 8 (bzw. -3).
Gruß Abakus

>  
>
> Gruß
>  
> D-C


Bezug
                
Bezug
Kongruenzen: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 22:51 Di 22.09.2009
Autor: D-C


> >
> > zu b)
>  >  
> > Wie geht man hier am besten vor?
>  Spätestens im 77. Versuch hast du die Lösung.
>  Da allerdings 76 [mm]\equiv[/mm] -1 mod 77, 75 [mm]\equiv[/mm] -2 mod 77 usw
> gilt, ist [mm]76^2 \equiv 1^2[/mm] mod 77,  [mm]75^2 \equiv 2^2[/mm] mod 77
> usw.
> Die Reste treten also paarweise auf, sodass du nur die
> Hälfte aller 77 Möglichkeiten testen musst.
>  Alternative: Addiere zu 8  so lange die Zahl 77, bis du
> eine Quadratzahl erhältst.
> 2. Alternative:
>  Eine Zahl, die bei Teilung durch 77 den Rest 8 lässt,
> lässt bei Teilung durch 7 den Rest 1 und bei ilung durch
> 11 den Rest 8 (bzw. -3).
>  Gruß Abakus
>  >  

Ok, werde mir das morgen nochmal in Ruhe anschauen.
Hab mir nur schonmal die 1. Alternative angeschaut, da müsste die erste Quadratzahl dann 6400 sein...

Gruß
D-C


Bezug
                
Bezug
Kongruenzen: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 16:46 Mi 23.09.2009
Autor: D-C


>  Mit einem endlichen Aufwand des Probierens von
> Möglichkeiten.
>  Vermutlich werden die Terme 6*1, 6*2, 6*3, ... 6*11
> allesamt  verschiedene Reste mod 11 liefern.
>  Da es nur 11 mögliche Reste gibt, hast du spätestens im
> 11. Versuch auch den gewünschten Rest 2.

Ja, es lassen sich alle Elemente 1,2,...,10 darstellen. Der Rest 2 ergibt sich bei [mm] 6^9 [/mm] = 1007796 = 2 mod 11.

Nur woran erkennt man,  dass das dann genau der gesuchte Rest ist?


>  Wenn man natürlich "sieht", dass 1 [mm]\equiv[/mm] 12 mod 11 ist
> und 12 durch 6 teilbar ist, kann man aus 6x [mm]\equiv[/mm] 1 mod 11
> sofort auf 6x [mm]\equiv[/mm] 12 mod 11 und damit auf die Lösung
> schließen.
>  

Also wenn man das "sieht", ist dann hier der Punkt, das aus der obigen Betrachtung und aus 12:6 die 2 als Ergebnis folgt?

Wie wäre es denn dann z.B. bei 12x [mm] \equiv [/mm] 5 mod 17 ?
Variante 1 wird durch Ausprobieren ab einer gewissen Größe ja ziemlich aufwendig. Lässt sich hier auch eine Alternative finden?


> > zu b)
>  >  
> > Wie geht man hier am besten vor?
>  Spätestens im 77. Versuch hast du die Lösung.
>  Da allerdings 76 [mm]\equiv[/mm] -1 mod 77, 75 [mm]\equiv[/mm] -2 mod 77 usw
> gilt, ist [mm]76^2 \equiv 1^2[/mm] mod 77,  [mm]75^2 \equiv 2^2[/mm] mod 77
> usw.
> Die Reste treten also paarweise auf, sodass du nur die
> Hälfte aller 77 Möglichkeiten testen musst.
>  Alternative: Addiere zu 8  so lange die Zahl 77, bis du
> eine Quadratzahl erhältst.
> 2. Alternative:
>  Eine Zahl, die bei Teilung durch 77 den Rest 8 lässt,
> lässt bei Teilung durch 7 den Rest 1 und bei ilung durch
> 11 den Rest 8 (bzw. -3).
>  Gruß Abakus
>  >  
> >
> > Gruß
>  >  
> > D-C
>  

Selbst wenn man nur die Hälfte betrachtet, ist das ja schon recht viel,
da scheint mir auf den ersten Blick die 1. Alternative schneller.
Bin hier auf 6400 als erste Quadratzahl gekommen. Wie gehts denn dann weiter?
Die 2. Alternative hab ich noch nicht so ganz verstanden, wie mich das weiterbringt..

Gruß

D-C

Bezug
                        
Bezug
Kongruenzen: Antwort
Status: (Antwort) fertig Status 
Datum: 17:07 Mi 23.09.2009
Autor: MathePower

Hallo D-C,

> >  Mit einem endlichen Aufwand des Probierens von

> > Möglichkeiten.
>  >  Vermutlich werden die Terme 6*1, 6*2, 6*3, ... 6*11
> > allesamt  verschiedene Reste mod 11 liefern.
>  >  Da es nur 11 mögliche Reste gibt, hast du spätestens
> im
> > 11. Versuch auch den gewünschten Rest 2.
>  
> Ja, es lassen sich alle Elemente 1,2,...,10 darstellen. Der
> Rest 2 ergibt sich bei [mm]6^9[/mm] = 1007796 = 2 mod 11.
>  
> Nur woran erkennt man,  dass das dann genau der gesuchte
> Rest ist?
>  


Nun, weil 2 das Inverse von 6 modulo 11 ist.


>
> >  Wenn man natürlich "sieht", dass 1 [mm]\equiv[/mm] 12 mod 11 ist

> > und 12 durch 6 teilbar ist, kann man aus 6x [mm]\equiv[/mm] 1 mod 11
> > sofort auf 6x [mm]\equiv[/mm] 12 mod 11 und damit auf die Lösung
> > schließen.
>  >  
>
> Also wenn man das "sieht", ist dann hier der Punkt, das aus
> der obigen Betrachtung und aus 12:6 die 2 als Ergebnis
> folgt?


Ja.


>  
> Wie wäre es denn dann z.B. bei 12x [mm]\equiv[/mm] 5 mod 17 ?
>  Variante 1 wird durch Ausprobieren ab einer gewissen
> Größe ja ziemlich aufwendig. Lässt sich hier auch eine
> Alternative finden?
>  


Die Idee ist immer dieselbe.

Berechne hier das Inverse von 12 modulo 17.

Das kannst Du mit Hilfe des Euklidischen Algorithmus tun.

Dann ergibt sich die Lösung zu: [mm]x \equiv 5*12^{-1}[/mm]

[mm]12^{-1}[/mm] bezeichnet eben dieses Inverse von 12 modulo 17.


>
> > > zu b)
>  >  >  
> > > Wie geht man hier am besten vor?
>  >  Spätestens im 77. Versuch hast du die Lösung.
>  >  Da allerdings 76 [mm]\equiv[/mm] -1 mod 77, 75 [mm]\equiv[/mm] -2 mod 77
> usw
> > gilt, ist [mm]76^2 \equiv 1^2[/mm] mod 77,  [mm]75^2 \equiv 2^2[/mm] mod 77
> > usw.
> > Die Reste treten also paarweise auf, sodass du nur die
> > Hälfte aller 77 Möglichkeiten testen musst.
>  >  Alternative: Addiere zu 8  so lange die Zahl 77, bis du
> > eine Quadratzahl erhältst.
> > 2. Alternative:
>  >  Eine Zahl, die bei Teilung durch 77 den Rest 8 lässt,
> > lässt bei Teilung durch 7 den Rest 1 und bei ilung durch
> > 11 den Rest 8 (bzw. -3).
>  >  Gruß Abakus
>  >  >  
> > >
> > > Gruß
>  >  >  
> > > D-C
> >  

>
> Selbst wenn man nur die Hälfte betrachtet, ist das ja
> schon recht viel,
>  da scheint mir auf den ersten Blick die 1. Alternative
> schneller.
>  Bin hier auf 6400 als erste Quadratzahl gekommen. Wie
> gehts denn dann weiter?


[mm]6400=80^{2}[/mm] läßt bei Division durch 77 nicht den Rest 8.


>  Die 2. Alternative hab ich noch nicht so ganz verstanden,
> wie mich das weiterbringt..


Nun berechne für [mm]x \equiv 0 ... 6[/mm] das Quadrat modulo 7.

Dasselbe machst Du für [mm]x \equiv 0 ... 10[/mm] das Quadrat modulo 11.


>  
> Gruß
>  
> D-C


Gruss
MathePower

Bezug
                                
Bezug
Kongruenzen: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 19:23 Mi 23.09.2009
Autor: D-C

Hi,

die a) ist mir dann soweit jetzt klar : )


> [mm]6400=80^{2}[/mm] läßt bei Division durch 77 nicht den Rest 8.

Dann hab ich mich da wohl irgendwo vertan....



> >  Die 2. Alternative hab ich noch nicht so ganz verstanden,

> > wie mich das weiterbringt..
>  
>
> Nun berechne für [mm]x \equiv 0 ... 6[/mm] das Quadrat modulo 7.
>  
> Dasselbe machst Du für [mm]x \equiv 0 ... 10[/mm] das Quadrat
> modulo 11.

Meinst Du damit:

[mm] 0^2 [/mm] = 0 mod 7
[mm] 1^2 [/mm] = 1 mod 7
[mm] 2^2 [/mm] = 4 mod 7
[mm] 3^2 [/mm] = 2 mod 7
[mm] 4^2 [/mm] = 2 mod 7
[mm] 5^2 [/mm] = 4 mod 7
[mm] 6^2 [/mm] = 1 mod 7

und

[mm] 0^2 [/mm] = 0 mod 11
[mm] 1^2 [/mm] = 1 mod 11
[mm] 2^2 [/mm] = 4 mod 11
[mm] 3^2 [/mm] = 9 mod 11
[mm] 4^2 [/mm] = 5 mod 11
[mm] 5^2 [/mm] = 3 mod 11
[mm] 6^2 [/mm] = 3 mod 11
[mm] 7^2 [/mm] = 5 mod 11
[mm] 8^2 [/mm] = 9 mod 11
[mm] 9^2 [/mm] = 4 mod 11
[mm] 10^2 [/mm] = 1 mod 11

Am Anfang hieß es ja:

[mm] x^2 \equiv [/mm] 8 mod 77 soll bedeuten:

> Eine Zahl, die bei Teilung durch 77 den Rest 8 lässt,
> lässt bei Teilung durch 7 den Rest 1 und bei Teilung durch
> 11 den Rest 8 (bzw. -3).

Die 7 und die 11 kommen wohl von der Zerlegung der 77 in Primfaktoren oder?
Ist es dann immer so, dass ein Rest 1 und der andere wie "vor" dem "mod angegeben ist ?

Schaue ich dann jetzt, wo bei den Quadraten mod 7 der Rest 1 ist und bei mod 11 der Rest 8 (bzw. -3) ist, oder wie geht es weiter?


Gruß

D-C



Bezug
                                        
Bezug
Kongruenzen: Antwort
Status: (Antwort) fertig Status 
Datum: 19:39 Mi 23.09.2009
Autor: MathePower

Hallo D-C,


> Hi,
>  
> die a) ist mir dann soweit jetzt klar : )
>  
>
> > [mm]6400=80^{2}[/mm] läßt bei Division durch 77 nicht den Rest 8.
>  
> Dann hab ich mich da wohl irgendwo vertan....
>  
>
>
> > >  Die 2. Alternative hab ich noch nicht so ganz verstanden,

> > > wie mich das weiterbringt..
>  >  
> >
> > Nun berechne für [mm]x \equiv 0 ... 6[/mm] das Quadrat modulo 7.
>  >  
> > Dasselbe machst Du für [mm]x \equiv 0 ... 10[/mm] das Quadrat
> > modulo 11.
>  
> Meinst Du damit:
>  
> [mm]0^2[/mm] = 0 mod 7
>  [mm]1^2[/mm] = 1 mod 7
>  [mm]2^2[/mm] = 4 mod 7
>  [mm]3^2[/mm] = 2 mod 7
>  [mm]4^2[/mm] = 2 mod 7
>  [mm]5^2[/mm] = 4 mod 7
>  [mm]6^2[/mm] = 1 mod 7
>  
> und
>  
> [mm]0^2[/mm] = 0 mod 11
>  [mm]1^2[/mm] = 1 mod 11
>  [mm]2^2[/mm] = 4 mod 11
>  [mm]3^2[/mm] = 9 mod 11
>  [mm]4^2[/mm] = 5 mod 11
>  [mm]5^2[/mm] = 3 mod 11
>  [mm]6^2[/mm] = 3 mod 11
>  [mm]7^2[/mm] = 5 mod 11
>  [mm]8^2[/mm] = 9 mod 11
>  [mm]9^2[/mm] = 4 mod 11
>  [mm]10^2[/mm] = 1 mod 11


Genau.


>  
> Am Anfang hieß es ja:
>  
> [mm]x^2 \equiv[/mm] 8 mod 77 soll bedeuten:
>  
> > Eine Zahl, die bei Teilung durch 77 den Rest 8 lässt,
> > lässt bei Teilung durch 7 den Rest 1 und bei Teilung durch
> > 11 den Rest 8 (bzw. -3).
>
> Die 7 und die 11 kommen wohl von der Zerlegung der 77 in
> Primfaktoren oder?


Ja, klar.


>  Ist es dann immer so, dass ein Rest 1 und der andere wie
> "vor" dem "mod angegeben ist ?


Nein.

Nehme hier zum Beispiel die Kongruenz

[mm]x^{2} \equiv 13 \ \left(77\right)[/mm]

Dann muß gelten:

[mm]x^{2} \equiv 13 \equiv 6 \ \left(7\right)[/mm]

[mm]x^{2} \equiv 13 \equiv 2 \ \left(11\right)[/mm]


>  
> Schaue ich dann jetzt, wo bei den Quadraten mod 7 der Rest
> 1 ist und bei mod 11 der Rest 8 (bzw. -3) ist, oder wie
> geht es weiter?
>  


Jetzt schaust Du danach, wo die entsprechenden Reste sind.



>
> Gruß
>  
> D-C
>  
>  

Bezug
                                                
Bezug
Kongruenzen: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 20:42 Mi 23.09.2009
Autor: D-C

Hi,

es geht voran : )

> Nehme hier zum Beispiel die Kongruenz
>  
> [mm]x^{2} \equiv 13 \ \left(77\right)[/mm]
>  
> Dann muß gelten:
>  
> [mm]x^{2} \equiv 13 \equiv 6 \ \left(7\right)[/mm]
>  
> [mm]x^{2} \equiv 13 \equiv 2 \ \left(11\right)[/mm]


Ok, jetzt ist mir das klar.



> > Schaue ich dann jetzt, wo bei den Quadraten mod 7 der Rest
> > 1 ist und bei mod 11 der Rest 8 (bzw. -3) ist, oder wie
> > geht es weiter?
>  >  
>
>
> Jetzt schaust Du danach, wo die entsprechenden Reste sind.


Die entsprechenden Reste müssten dann bei den Quadraten von mod7
bei [mm] 1^2 [/mm] und [mm] 6^2 [/mm]

sowie bei mod 11
bei  [mm] 5^2 [/mm] und [mm] 6^2 [/mm]

liegen. Jetzt fehlt mir nur noch irgendwie der letzte Schluss, der mich zur Lösung bringt..


Gruß
D-C





Bezug
                                                        
Bezug
Kongruenzen: Antwort
Status: (Antwort) fertig Status 
Datum: 20:49 Mi 23.09.2009
Autor: MathePower

Hallo D-C,

> Hi,
>  
> es geht voran : )
>  
> > Nehme hier zum Beispiel die Kongruenz
>  >  
> > [mm]x^{2} \equiv 13 \ \left(77\right)[/mm]
>  >  
> > Dann muß gelten:
>  >  
> > [mm]x^{2} \equiv 13 \equiv 6 \ \left(7\right)[/mm]
>  >  
> > [mm]x^{2} \equiv 13 \equiv 2 \ \left(11\right)[/mm]
>  
>
> Ok, jetzt ist mir das klar.
>
>
>
> > > Schaue ich dann jetzt, wo bei den Quadraten mod 7 der Rest
> > > 1 ist und bei mod 11 der Rest 8 (bzw. -3) ist, oder wie
> > > geht es weiter?
>  >  >  
> >
> >
> > Jetzt schaust Du danach, wo die entsprechenden Reste sind.
>  
>
> Die entsprechenden Reste müssten dann bei den Quadraten
> von mod7
>  bei [mm]1^2[/mm] und [mm]6^2[/mm]


[ok]


>  
> sowie bei mod 11
>  bei  [mm]5^2[/mm] und [mm]6^2[/mm]


Das stimmt nicht: [mm]5^{2}=25 \equiv 3 \not= 8 \ \left(11\right)[/mm]


>  
> liegen. Jetzt fehlt mir nur noch irgendwie der letzte
> Schluss, der mich zur Lösung bringt..
>  
>
> Gruß
>  D-C
>  


Gruss
MathePower

Bezug
                                                                
Bezug
Kongruenzen: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 21:09 Mi 23.09.2009
Autor: D-C

Hi,

> > Die entsprechenden Reste müssten dann bei den Quadraten
> > von mod7
>  >  bei [mm]1^2[/mm] und [mm]6^2[/mm]
>  
> [ok]
>  
> > sowie bei mod 11
>  >  bei  [mm]5^2[/mm] und [mm]6^2[/mm]
>  

> Das stimmt nicht: [mm]5^{2}=25 \equiv 3 \not= 8 \ \left(11\right)[/mm]

Achso, ich hab hier die 3 zu Grunde gelegt, ein Rest 8 kommt dann hier wohl nicht vor....

> > Jetzt fehlt mir nur noch irgendwie der letzte
> > Schluss, der mich zur Lösung bringt..

Gruß
D-C


Bezug
                                                                        
Bezug
Kongruenzen: Antwort
Status: (Antwort) fertig Status 
Datum: 21:22 Mi 23.09.2009
Autor: MathePower

Hallo D-C,

> Hi,
>  
> > > Die entsprechenden Reste müssten dann bei den Quadraten
> > > von mod7
>  >  >  bei [mm]1^2[/mm] und [mm]6^2[/mm]
>  >  
> > [ok]
>  >  
> > > sowie bei mod 11
>  >  >  bei  [mm]5^2[/mm] und [mm]6^2[/mm]
>  >  
>
> > Das stimmt nicht: [mm]5^{2}=25 \equiv 3 \not= 8 \ \left(11\right)[/mm]
>
> Achso, ich hab hier die 3 zu Grunde gelegt, ein Rest 8
> kommt dann hier wohl nicht vor....


Das heißt dann, daß die Kongruenz [mm]x^{2} \equiv 8 \ \left(77\right)[/mm] keine Lösung besitzt.


>  
> > > Jetzt fehlt mir nur noch irgendwie der letzte
> > > Schluss, der mich zur Lösung bringt..
>  
> Gruß
>  D-C

>


Gruss
MathePower  

Bezug
                                                                                
Bezug
Kongruenzen: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 21:35 Mi 23.09.2009
Autor: D-C

Hi,

> Das heißt dann, daß die Kongruenz [mm]x^{2} \equiv 8 \ \left(77\right)[/mm]
> keine Lösung besitzt.


Ok, das wäre dann also die Antwort zu der Aufgabe?

D.h. immer wenn in mindestens einem der beiden modulo (hier 7 und 11) kein passender Rest zu finden ist, gibt es auch keine Lösung!?

Im anderen Fall, wären dann alle die gefundenen Reste die Lösungen?

Gruß

D-C



Bezug
                                                                                        
Bezug
Kongruenzen: Antwort
Status: (Antwort) fertig Status 
Datum: 21:42 Mi 23.09.2009
Autor: MathePower

Hallo D-C,

> Hi,
>  
> > Das heißt dann, daß die Kongruenz [mm]x^{2} \equiv 8 \ \left(77\right)[/mm]
> > keine Lösung besitzt.
>  
>
> Ok, das wäre dann also die Antwort zu der Aufgabe?


Ja.


>  
> D.h. immer wenn in mindestens einem der beiden modulo (hier
> 7 und 11) kein passender Rest zu finden ist, gibt es auch
> keine Lösung!?
>  
> Im anderen Fall, wären dann alle die gefundenen Reste die
> Lösungen?


Die gefundenen Reste bilden ein Kongruenzsystem (hier mit 7 und 11)

[mm]x \equiv a \ \left(7\right)[/mm]

[mm]x \equiv b \ \left(11\right)[/mm]

deren Lösungen mit dem []chinesischen Restsatz ermittelt werden können.

Natürlich mußt Du das für alle möglichen Reste machen.


>  
> Gruß
>  
> D-C
>  
>  


Gruss
MathePower

Bezug
                                                                                                
Bezug
Kongruenzen: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 22:15 Mi 23.09.2009
Autor: D-C

Ok, dann erstmal danke für die Hilfe : )

Stimmt, wenn es hier passende Reste gegeben hätte, kann man dann den chinesischen Restsatz anwenden, da Teilerfremdheit ja gegeben ist..

Mal sehen, ob ich morgen mal noch ein Beispiel finde, wo es passende Reste gibt.

Alles in allem ist wohl der letzte Weg, der einfachere wenn man ihn erstmal kennt : ) das andere ist ja mehr ein ausprobieren, was wohl nur bei kleinen Zahlen lohnt..

Gruß

D-C

Bezug
                                                                                                
Bezug
Kongruenzen: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 19:29 Do 24.09.2009
Autor: D-C

Hi,

nochmal eine kurze Nachfrage ; )

> Die gefundenen Reste bilden ein Kongruenzsystem (hier mit 7
> und 11)
>  
> [mm]x \equiv a \ \left(7\right)[/mm]
>  
> [mm]x \equiv b \ \left(11\right)[/mm]
>  
> deren Lösungen mit dem
> []chinesischen Restsatz
> ermittelt werden können.
>  
> Natürlich mußt Du das für alle möglichen Reste machen.

Also für a setze ich alle passenden Reste aus mod 7 ein
und bei b entsprechen alle aus mod 11.

Es kann ja aber auch passieren, dass ich mehrere Reste habe

also z.b.

x [mm] \equiv [/mm] 1 mod 7
x [mm] \equiv [/mm] 6 mod 7
x [mm] \equiv [/mm] 8 mod 11

7 wäre ja dann von 7 nicht teilerfremd und daher ließe sich
der chinesische Restsatz erstmal nicht anwenden. Folglich
müsste ich also in dem Fall, wo mehrere Reste existieren, dann
das System noch soweit umstellen, bis ich den Satz anwenden kann,
oder ist mein Ansatz falsch!?

Gruß

D-C

Bezug
                                                                                                        
Bezug
Kongruenzen: Antwort
Status: (Antwort) fertig Status 
Datum: 20:16 Do 24.09.2009
Autor: MathePower

Hallo D-C,

> Hi,
>  
> nochmal eine kurze Nachfrage ; )
>  
> > Die gefundenen Reste bilden ein Kongruenzsystem (hier mit 7
> > und 11)
>  >  
> > [mm]x \equiv a \ \left(7\right)[/mm]
>  >  
> > [mm]x \equiv b \ \left(11\right)[/mm]
>  >  
> > deren Lösungen mit dem
> > []chinesischen Restsatz
> > ermittelt werden können.
>  >  
> > Natürlich mußt Du das für alle möglichen Reste machen.
>  
> Also für a setze ich alle passenden Reste aus mod 7 ein
>  und bei b entsprechen alle aus mod 11.
>  


Hier mußt jeden Rest aus mod 7 mit jedem Rest aus mod 11 kombinieren.


> Es kann ja aber auch passieren, dass ich mehrere Reste
> habe
>  
> also z.b.
>  
> x [mm]\equiv[/mm] 1 mod 7
>  x [mm]\equiv[/mm] 6 mod 7
>  x [mm]\equiv[/mm] 8 mod 11
>  
> 7 wäre ja dann von 7 nicht teilerfremd und daher ließe
> sich
>  der chinesische Restsatz erstmal nicht anwenden. Folglich
>  müsste ich also in dem Fall, wo mehrere Reste existieren,
> dann
> das System noch soweit umstellen, bis ich den Satz anwenden
> kann,
>  oder ist mein Ansatz falsch!?


Wenn Du mehrere Reste hast, hast Du dementsprechend
viele Kongruenzsysteme zu lösen.

1. Kongruenzsystem:

[mm]x \equiv 1 \ \operatorname{mod} \ 7[/mm]
[mm]x \equiv 8 \ \operatorname{mod} \ 11[/mm]

2. Kongruenzsystem:

[mm]x \equiv 6 \ \operatorname{mod} \ 7[/mm]
[mm]x \equiv 8 \ \operatorname{mod} \ 11[/mm]


>
>  
> Gruß
>  
> D-C


Gruss
MathePower

Bezug
                                                                                                                
Bezug
Kongruenzen: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 21:17 Do 24.09.2009
Autor: D-C

Ah ok, das "teilt" sich also auf..

Gruß

D-C

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


^ Seitenanfang ^
www.matheraum.de
[ Startseite | Forum | Wissen | Kurse | Mitglieder | Team | Impressum ]