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
StartseiteMatheForenZahlentheorieKongruenz lösen
Foren für weitere Studienfächer findest Du auf www.vorhilfe.de z.B. Astronomie • Medizin • Elektrotechnik • Maschinenbau • Bauingenieurwesen • Jura • Psychologie • Geowissenschaften
Forum "Zahlentheorie" - Kongruenz lösen
Kongruenz lösen < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Zahlentheorie"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Kongruenz lösen: Aufgabe
Status: (Frage) beantwortet Status 
Datum: 14:48 So 26.05.2013
Autor: Kate-Mary

Aufgabe
Berechne alle Lösungen der Kongruenz [mm] 27x\equiv72 [/mm] (mod 900).

Hallo!

Ich habe bis jetzt folgendes gemacht:
Mit Hilfe des euklidischen Algorithmus den ggT(27,135) ausgerechnet:
900=33*27+9
27=3*9 [mm] \Rightarrow [/mm] ggT(27,135)=9

Jetzt hab ich geteilt:
27x [mm] \equiv [/mm] 72 (mod 900) [mm] \Leftrightarrow [/mm] 3x [mm] \equiv [/mm] 8 (mod 10)

Wenn ich jetzt wieder den ggT ausrechne, also ggT(3,10)
10=3*3+1
3=1*3+0 [mm] \Rightarrow [/mm] ggT(3,10)=1 (da 3 prim)

Allerdings weiß ich nicht wirklich, was ich jetzt machen soll.

Kann mir jemand helfen?

Liebe Grüße,
Kate-Mary


        
Bezug
Kongruenz lösen: Antwort
Status: (Antwort) fertig Status 
Datum: 15:18 So 26.05.2013
Autor: reverend

Hallo Kate-Mary,

da sind Fehler drin, die ich mir nicht erklären kann. Hast Du zwei Aufgaben vermischt?

> Berechne alle Lösungen der Kongruenz [mm]27x\equiv72[/mm] (mod
> 900).
> Hallo!

>

> Ich habe bis jetzt folgendes gemacht:
> Mit Hilfe des euklidischen Algorithmus den ggT(27,135)
> ausgerechnet:

Wozu? Woher kommt die 135? Da 135=5*27 ist, ist der ggT(27,135)=27.

> 900=33*27+9
> 27=3*9 [mm]\Rightarrow[/mm] ggT(27,135)=9

Interessant ist hier doch der ggT(27,72,900)=9.

> Jetzt hab ich geteilt:
> 27x [mm]\equiv[/mm] 72 (mod 900) [mm]\Leftrightarrow[/mm] 3x [mm]\equiv[/mm] 8 (mod
> 10)

Wieso mod 10? Das müsste doch mod 100 heißen.

> Wenn ich jetzt wieder den ggT ausrechne, also ggT(3,10)
> 10=3*3+1
> 3=1*3+0 [mm]\Rightarrow[/mm] ggT(3,10)=1 (da 3 prim)

Das ist ein unnötiger Schritt, wenn Du vorher den ggT(27,900) richtig bestimmt hast. Dann muss hier ja auf jeden Fall 1 herauskommen.

> Allerdings weiß ich nicht wirklich, was ich jetzt machen
> soll.

Löse [mm] 3x\equiv 8\mod{(100)}. [/mm]
Bilde dazu das multiplikativ Inverse von [mm] 3\mod{(100)}. [/mm] Wahrscheinlich sollst Du das hier ganz formal tun; man kann es ja auch ganz leicht per Kopfrechnung finden.

> Kann mir jemand helfen?

Na, hoffentlich. ;-)
Grüße
reverend

Bezug
                
Bezug
Kongruenz lösen: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 15:46 So 26.05.2013
Autor: Kate-Mary

Ups...okay, erst zu blöd zum abschreiben, weil ich verrutscht bin und dann auch noch zu blöd zum rechnen...

also es muss natürlich ggT(27,900)=9 heißen und 900/9 ist natürlich auch 100...

>  >
>  > Ich habe bis jetzt folgendes gemacht:

>  > Mit Hilfe des euklidischen Algorithmus den ggT(27,135)

>  > ausgerechnet:

>  
> Wozu? Woher kommt die 135? Da 135=5*27 ist, ist der
> ggT(27,135)=27.
>  
> > 900=33*27+9
>  > 27=3*9 [mm]\Rightarrow[/mm] ggT(27,135)=9

>  
> Interessant ist hier doch der ggT(27,72,900)=9.
>  

...

>  
> Wieso mod 10? Das müsste doch mod 100 heißen.
>  

>  
>  
> Löse [mm]3x\equiv 8\mod{(100)}.[/mm]
>  Bilde dazu das multiplikativ
> Inverse von [mm]3\mod{(100)}.[/mm] Wahrscheinlich sollst Du das hier
> ganz formal tun; man kann es ja auch ganz leicht per
> Kopfrechnung finden.

Kannst du mir erklären, warum ich das multiplikativ Inverse zu 3 mod (100) bilden muss? Weil da wär ich selber von nie drauf gekommen.

Aber hier schon mal meine Lösung (ich hoffe diesmal ohne Fehler ;) )
1. ggT(3,100):

100=33*3+1
3=3*1+0  [mm] \Rightarrow [/mm] ggT(3,100)=1

2. Umkehrung:
1=100-33*3

Aber irgendwie seh ich immernoch nicht wirklich, was mir das helfen soll. Oder hab ich das Inverse falsch berechnet??


Bezug
                        
Bezug
Kongruenz lösen: Antwort
Status: (Antwort) fertig Status 
Datum: 15:54 So 26.05.2013
Autor: MathePower

Hallo Kate-Mary,

> Ups...okay, erst zu blöd zum abschreiben, weil ich
> verrutscht bin und dann auch noch zu blöd zum rechnen...
>  
> also es muss natürlich ggT(27,900)=9 heißen und 900/9 ist
> natürlich auch 100...
>  
> >  >

>  >  > Ich habe bis jetzt folgendes gemacht:

>  >  > Mit Hilfe des euklidischen Algorithmus den

> ggT(27,135)
>  >  > ausgerechnet:

>  >  
> > Wozu? Woher kommt die 135? Da 135=5*27 ist, ist der
> > ggT(27,135)=27.
>  >  
> > > 900=33*27+9
>  >  > 27=3*9 [mm]\Rightarrow[/mm] ggT(27,135)=9

>  >  
> > Interessant ist hier doch der ggT(27,72,900)=9.
>  >  
> ...
>  >  
> > Wieso mod 10? Das müsste doch mod 100 heißen.
>  >  
>
> >  

> >  

> > Löse [mm]3x\equiv 8\mod{(100)}.[/mm]
>  >  Bilde dazu das
> multiplikativ
> > Inverse von [mm]3\mod{(100)}.[/mm] Wahrscheinlich sollst Du das hier
> > ganz formal tun; man kann es ja auch ganz leicht per
> > Kopfrechnung finden.
>  
> Kannst du mir erklären, warum ich das multiplikativ
> Inverse zu 3 mod (100) bilden muss? Weil da wär ich selber
> von nie drauf gekommen.
>  


Weil 3 multipliziert mit dem multiplikativ
Inversen zu 3 den 100er 1 lässt.


> Aber hier schon mal meine Lösung (ich hoffe diesmal ohne
> Fehler ;) )
>  1. ggT(3,100):
>  
> 100=33*3+1
>  3=3*1+0  [mm]\Rightarrow[/mm] ggT(3,100)=1
>  
> 2. Umkehrung:
>  1=100-33*3
>  
> Aber irgendwie seh ich immernoch nicht wirklich, was mir
> das helfen soll. Oder hab ich das Inverse falsch
> berechnet??

>

Multipliziere doch die Ausgangsgleichung mit diesem multiplikativ Inversen zu 3.

Dann hast Du da stehen: [mm]x\equiv 8*3^{-1}\mod{(100)}[/mm]

[mm]3^{-1}[/mm] ist das multiplikativ Inverse zu 3.


Gruss
MathePower  

Bezug
                                
Bezug
Kongruenz lösen: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 16:06 So 26.05.2013
Autor: Kate-Mary

Also irgendwie steh ich grad ziemlich auf dem Schlauch:

Nach Umformung der ursprünglichen Gleichung hab ich [mm] 3x\equiv [/mm] 8 mod (100) herausbekommen.
Logisch ist, dass ich jetzt diese Gleichung lösen muss.
reverend hat mir dazu den Tipp gegeben, dass ich das Multiplikative von 3 mod (100) berechnen soll.
Die Erklärung

>
> Weil 3 multipliziert mit dem multiplikativ
>  Inversen zu 3 den 100er 1 lässt.
>  

versteh ich irgendwie nicht so ganz :(

>  
> Multipliziere doch die Ausgangsgleichung mit diesem
> multiplikativ Inversen zu 3.
>  
> Dann hast Du da stehen: [mm]x\equiv 8*3^{-1}\mod{(100)}[/mm]
>  
> [mm]3^{-1}[/mm] ist das multiplikativ Inverse zu 3.
>  

soll ich da jetzt für 3^-1 noch was einsetzen oder wie ist das zu verstehen?

LG


Bezug
                                        
Bezug
Kongruenz lösen: Antwort
Status: (Antwort) fertig Status 
Datum: 16:17 So 26.05.2013
Autor: MathePower

Hallo Kate-Mary,

> Also irgendwie steh ich grad ziemlich auf dem Schlauch:
>  
> Nach Umformung der ursprünglichen Gleichung hab ich
> [mm]3x\equiv[/mm] 8 mod (100) herausbekommen.
>  Logisch ist, dass ich jetzt diese Gleichung lösen muss.
>  reverend hat mir dazu den Tipp gegeben, dass ich das
> Multiplikative von 3 mod (100) berechnen soll.
>  Die Erklärung
>  >

> > Weil 3 multipliziert mit dem multiplikativ
>  >  Inversen zu 3 den 100er 1 lässt.
>  >  
> versteh ich irgendwie nicht so ganz :(
>  


Nun Du hast weiter unten das multiplikativ Inverse zu 3 mit -33 berechnet.
3*(-33)=-99=-100+1.

Damit lässt dies den 100er Rest 1.

Daher lautet jetzt die neue Gleichung:

[mm]3*(-33) x \equiv 1*x \equiv 8*(-33) \ \operatorname{mod} \left(100\right)[/mm]


> >  

> > Multipliziere doch die Ausgangsgleichung mit diesem
> > multiplikativ Inversen zu 3.
>  >  
> > Dann hast Du da stehen: [mm]x\equiv 8*3^{-1}\mod{(100)}[/mm]
>  >  
> > [mm]3^{-1}[/mm] ist das multiplikativ Inverse zu 3.
>  >  
> soll ich da jetzt für 3^-1 noch was einsetzen oder wie ist
> das zu verstehen?

>


Setze für [mm]3^{-1}[/mm] das berechnete multiplikativ Inverse -33 ein.

  

> LG

>


Grus
MathePower  

Bezug
                                                
Bezug
Kongruenz lösen: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 16:28 So 26.05.2013
Autor: Kate-Mary

Okay, soweit versteh ich das jetzt,

wenn ich jetzt in [mm] x\equiv 8*3^{-1} [/mm] mod (100) für [mm] 3^{-1} [/mm] -33 einsetze und dass ausrechne, dann kommt
[mm] x\equiv [/mm] -264 mod 100 raus.

Und das soll jetzt die Lösung sein?
Geb ich die Lösung dann folgendermaßen angeben?
[mm] \IL= [/mm] { -264+100z; [mm] z\in \IZ [/mm] }

LG


Bezug
                                                        
Bezug
Kongruenz lösen: Antwort
Status: (Antwort) fertig Status 
Datum: 16:40 So 26.05.2013
Autor: MathePower

Hallo Kate-Mary,

> Okay, soweit versteh ich das jetzt,
>  
> wenn ich jetzt in [mm]x\equiv 8*3^{-1}[/mm] mod (100) für [mm]3^{-1}[/mm]
> -33 einsetze und dass ausrechne, dann kommt
>   [mm]x\equiv[/mm] -264 mod 100 raus.
>  
> Und das soll jetzt die Lösung sein?


Ja, das ist die Lösung.


>  Geb ich die Lösung dann folgendermaßen angeben?
>  [mm]\IL=\{ -264+100z; \ z \in \IZ \}[/mm]

>


Ja.

  

> LG

>


Gruss
MathePower  

Bezug
                                                                
Bezug
Kongruenz lösen: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 17:01 So 26.05.2013
Autor: Kate-Mary

Aufgabe
Berechne alle Lösungen 9x [mm] \equiv [/mm] 12 mod 12

Danke.

Oben steht noch eine zweite Aufgabe, die analog laufen sollte. Ich hab das mal schnell durchgerechnet.
Kannst du mir sagen, ob das so richtig ist?

9x [mm] \equiv [/mm] 12 mod 12

ggT (9,12)
12=1*9+3
9=3*3+0 [mm] \Rightarrow [/mm] ggT(9,12)=3

9x [mm] \equiv [/mm] 12 mod 12 [mm] \Leftrightarrow [/mm] 3x [mm] \equiv [/mm] 4 mod 4

Multiplikativ Inverses zu 3 mod 4:
4=1*3+1
3=3*1+0 [mm] \Rightarrow [/mm] ggT(3,4)=1
[mm] \Rightarrow [/mm] 1=4-3*1

[mm] \Rightarrow x\equiv [/mm] 4*(-4) mod 4 =-12 mod 4

[mm] \Rightarrow \IL= [/mm] {-12+4z ; [mm] z\in \IZ [/mm] }

LG

Bezug
                                                                        
Bezug
Kongruenz lösen: Antwort
Status: (Antwort) fertig Status 
Datum: 17:13 So 26.05.2013
Autor: MathePower

Hallo Kate-Mary,

> Berechne alle Lösungen 9x [mm]\equiv[/mm] 12 mod 12
>  Danke.
>  
> Oben steht noch eine zweite Aufgabe, die analog laufen
> sollte. Ich hab das mal schnell durchgerechnet.
>  Kannst du mir sagen, ob das so richtig ist?
>  
> 9x [mm]\equiv[/mm] 12 mod 12
>  
> ggT (9,12)
>  12=1*9+3
>  9=3*3+0 [mm]\Rightarrow[/mm] ggT(9,12)=3
>  
> 9x [mm]\equiv[/mm] 12 mod 12 [mm]\Leftrightarrow[/mm] 3x [mm]\equiv[/mm] 4 mod 4
>  
> Multiplikativ Inverses zu 3 mod 4:
>  4=1*3+1
>  3=3*1+0 [mm]\Rightarrow[/mm] ggT(3,4)=1
>  [mm]\Rightarrow[/mm] 1=4-3*1
>  
> [mm]\Rightarrow x\equiv[/mm] 4*(-4) mod 4 =-12 mod 4
>  
> [mm]\Rightarrow \IL=[/mm]Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)

{-12+4z ; [mm]z\in \IZ[/mm]Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)

}

>  


Oder besser, da -12 ein Vielfaches von 4 ist:

[mm]\IL=\{4z ; z\in \IZ \}[/mm]


> LG


Gruss
MathePower

Bezug
                                                                        
Bezug
Kongruenz lösen: Antwort
Status: (Antwort) fertig Status 
Datum: 17:20 So 26.05.2013
Autor: abakus


> Berechne alle Lösungen 9x [mm]\equiv[/mm] 12 mod 12
> Danke.

>

> Oben steht noch eine zweite Aufgabe, die analog laufen
> sollte. Ich hab das mal schnell durchgerechnet.
> Kannst du mir sagen, ob das so richtig ist?

>

> 9x [mm]\equiv[/mm] 12 mod 12

Hallo,
Es gilt doch 12 [mm]\equiv[/mm] 0 mod 12.
Daraus folgt also 9x [mm]\equiv[/mm] 0 mod 12 oder 
"9x ist durch 12 teilbar".
Da 9 durch 3 teilbar ist, muss x einfach nur durch 4 teilbar sein.
Gruß Abakus

>

> ggT (9,12)
> 12=1*9+3
> 9=3*3+0 [mm]\Rightarrow[/mm] ggT(9,12)=3

>

> 9x [mm]\equiv[/mm] 12 mod 12 [mm]\Leftrightarrow[/mm] 3x [mm]\equiv[/mm] 4 mod 4

>

> Multiplikativ Inverses zu 3 mod 4:
> 4=1*3+1
> 3=3*1+0 [mm]\Rightarrow[/mm] ggT(3,4)=1
> [mm]\Rightarrow[/mm] 1=4-3*1

>

> [mm]\Rightarrow x\equiv[/mm] 4*(-4) mod 4 =-12 mod 4

>

> [mm]\Rightarrow \IL=[/mm]Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)

{-12+4z ; [mm]z\in \IZ[/mm]Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)

}
>

> LG

Bezug
                                                                                
Bezug
Kongruenz lösen: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 18:01 So 26.05.2013
Autor: Marcel

Hi Abakus,

>  > 9x [mm]\equiv[/mm] 12 mod 12

>  
> Hallo,
>  Es gilt doch 12 [mm]\equiv[/mm] 0 mod 12.
>  Daraus folgt also 9x [mm]\equiv[/mm] 0 mod 12 oder 
>  "9x ist durch 12 teilbar".

ich würde sowieso gerne mal generell drauf hinweisen:
Für $a,b,p,q [mm] \in \IZ$ [/mm] und $n [mm] \in \IN$ [/mm] gilt
$$a [mm] \equiv [/mm] b [mm] \mod [/mm] n$$
[mm] $$\iff [/mm] a+p*n [mm] \equiv [/mm] b+q*n [mm] \mod [/mm] n$$

>  Da 9 durch 3 teilbar ist, muss x einfach nur durch 4
> teilbar sein.

Gruß,
  Marcel

Bezug
                                                                                
Bezug
Kongruenz lösen: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 18:02 So 26.05.2013
Autor: Kate-Mary

Ja, das ist klar. Ich wollte aber die Aufgabe analog zur vorherigen lösen, um zu schaun, ob ich alle skapiert habe. Trotzdem Danke.

Danke auch an MathePower!!

Bezug
                                                                                        
Bezug
Kongruenz lösen: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 18:08 So 26.05.2013
Autor: Marcel

Hallo,

> ... um zu schaun, ob ich
> alle skapiert habe.

ich hoffe, Du wolltest nicht alle [mm] ska$\red{\ell}$pieren [/mm] ^^ ;-)

Gruß,
  Marcel

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


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