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" - mod
mod < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Zahlentheorie"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

mod: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 14:24 Di 26.11.2013
Autor: kRAITOS

Aufgabe
b) Bestimmen Sie für p [mm] \in [/mm] {23,53,89} die ganze Zahl x [mm] \in [/mm] {0, ..., p−1}, für die
13 · x ≡ 1 mod p
gilt.


c) Bestimmen Sie jeweils die ganze Zahl x [mm] \in \IZ [/mm] mit den geforderten Eigenschaften:

• [mm] 5^3 [/mm] ≡ x mod3, 0 ≤ x ≤ 2,
• [mm] 4^5 [/mm] ≡ x mod5, 0 ≤ x ≤ 4,
• [mm] 11^7 [/mm] ≡ x mod7, 0 ≤ x ≤ 6,
• 9^11 ≡ x mod11, 0 ≤ x ≤ 10,
• 2^12 ≡ x mod13, 0 ≤ x ≤ 12.


Hallo.

Kann mir jemand sagen, was ich hier machen muss? Habe gerade das Internet durchsucht aber ich finde irgendwie nichts passendes, was mir hier weiterhilft.


Danke schonmal.

        
Bezug
mod: Antwort
Status: (Antwort) fertig Status 
Datum: 14:33 Di 26.11.2013
Autor: schachuzipus

Hallo,

> b) Bestimmen Sie für p [mm]\in[/mm] {23,53,89} die ganze Zahl x [mm]\in[/mm]
> {0, ..., p−1}, für die
> 13 · x ≡ 1 mod p
> gilt.

>
>

> c) Bestimmen Sie jeweils die ganze Zahl x [mm]\in \IZ[/mm] mit den
> geforderten Eigenschaften:

>

> • 53 ≡ x mod3, 0 ≤ x ≤ 2,
> • 45 ≡ x mod5, 0 ≤ x ≤ 4,
> • 117 ≡ x mod7, 0 ≤ x ≤ 6,
> • 911 ≡ x mod11, 0 ≤ x ≤ 10,
> • 212 ≡ x mod13, 0 ≤ x ≤ 12.
> Hallo.

>

> Kann mir jemand sagen, was ich hier machen muss? Habe
> gerade das Internet durchsucht aber ich finde irgendwie
> nichts passendes, was mir hier weiterhilft.

Vllt findest du was in deiner Vorlesungsmitschrift?

Wieso bekommt ihr immer Aufgaben, von denen du noch nie vorher was gesehen hast? Hat eure Uni ein ganz besonderes Lernkonzept?

In a) gilt es jeweils die multiplikativ Inversen von 13 zu bestimmen mod 23, mod 53 und mod 89.

Schaue dir in diesem Zusammenhang mal den Euklidischen Algorithmus an ... 

Hast du gesehen, dass alle Moduln prim sind?

Bei c)

Erste Aufgabe: Was bedeutet denn [mm]53\equiv x \ \mod(3)[/mm]?

Wenn dir das nicht klar ist, kannst du die Aufgaben nicht lösen ...

Also mache dich in deiner VL-Mitschrift schlau. Ohne Definition bzw. Verständnis des [mm]\equiv[/mm] wird das sonst nix ...


>
>

> Danke schonmal.

Gruß

schachuzipus

Bezug
                
Bezug
mod: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 17:16 Di 26.11.2013
Autor: kRAITOS


> Hallo,
>  
> > b) Bestimmen Sie für p [mm]\in[/mm] {23,53,89} die ganze Zahl x
> [mm]\in[/mm]
>  > {0, ..., p−1}, für die

>  > 13 · x ≡ 1 mod p

>  > gilt.

>  >
>  >
>  > c) Bestimmen Sie jeweils die ganze Zahl x [mm]\in \IZ[/mm] mit

> den
>  > geforderten Eigenschaften:

>  >
>  > • 53 ≡ x mod3, 0 ≤ x ≤ 2,

>  > • 45 ≡ x mod5, 0 ≤ x ≤ 4,

>  > • 117 ≡ x mod7, 0 ≤ x ≤ 6,

>  > • 911 ≡ x mod11, 0 ≤ x ≤ 10,

>  > • 212 ≡ x mod13, 0 ≤ x ≤ 12.

>  > Hallo.

>  >
>  > Kann mir jemand sagen, was ich hier machen muss? Habe

>  > gerade das Internet durchsucht aber ich finde irgendwie

>  > nichts passendes, was mir hier weiterhilft.

>  
> Vllt findest du was in deiner Vorlesungsmitschrift?
>  
> Wieso bekommt ihr immer Aufgaben, von denen du noch nie
> vorher was gesehen hast? Hat eure Uni ein ganz besonderes
> Lernkonzept?
>  
> In a) gilt es jeweils die multiplikativ Inversen von 13 zu
> bestimmen mod 23, mod 53 und mod 89.
>  
> Schaue dir in diesem Zusammenhang mal den Euklidischen
> Algorithmus an ... 


Danke für die Information.


> Hast du gesehen, dass alle Moduln prim sind?
>  
> Bei c)
>  
> Erste Aufgabe: Was bedeutet denn [mm]53\equiv x \ \mod(3)[/mm]?
>  
> Wenn dir das nicht klar ist, kannst du die Aufgaben nicht
> lösen ...
>  
> Also mache dich in deiner VL-Mitschrift schlau. Ohne
> Definition bzw. Verständnis des [mm]\equiv[/mm] wird das sonst nix
> ...
>  
>
> >
>  >
>  > Danke schonmal.

>  
> Gruß
>  
> schachuzipus


In meinen Skripten steht leider nichts zu diesem Thema..

Aber ich habe ein paar schöne Definitionen gefunden.

2 Zahlen a,b [mm] \in \IZ [/mm] heißen kongruent modulo m wenn gilt:

a [mm] \equiv [/mm] b mod m.

Das heißt, beide Zahlen lassen durch teilen von m denselben Rest.

Desweiteren ist a [mm] \equiv [/mm] b mod m [mm] \gdw [/mm] (a-b) = 0


Also muss ich quasi ein x suchen aus dem gegebenen Definitionsbereich.


[mm] 5^3 [/mm] ≡ x mod3, 0 ≤ x ≤ 2

[mm] \gdw 5^3 [/mm] - x  = 0 mod 3
[mm] \gdw [/mm] 125-x mod 3 = 0

und mit x=2 wäre

125-2 mod 3 = 0  [mm] \gdw [/mm] 123 mod 3 = 0

Also ist das gesuchte x =2.

Jetzt habe ich aber noch eine Verständnisfrage:


9^11 ≡ x mod11, 0 ≤ x ≤ 10

9^11 = 31381059609

Gibt es hier irgendeinen Kniff, diese Aufgabe zu vereinfachen?

Bezug
                        
Bezug
mod: Antwort
Status: (Antwort) fertig Status 
Datum: 17:28 Di 26.11.2013
Autor: schachuzipus

Hallo nochmal,


> > Hallo,
> >
> > > b) Bestimmen Sie für p [mm]\in[/mm] {23,53,89} die ganze Zahl x
> > [mm]\in[/mm]
> > > {0, ..., p−1}, für die
> > > 13 · x ≡ 1 mod p
> > > gilt.
> > >
> > >
> > > c) Bestimmen Sie jeweils die ganze Zahl x [mm]\in \IZ[/mm] mit
> > den
> > > geforderten Eigenschaften:
> > >
> > > • 53 ≡ x mod3, 0 ≤ x ≤ 2,
> > > • 45 ≡ x mod5, 0 ≤ x ≤ 4,
> > > • 117 ≡ x mod7, 0 ≤ x ≤ 6,
> > > • 911 ≡ x mod11, 0 ≤ x ≤ 10,
> > > • 212 ≡ x mod13, 0 ≤ x ≤ 12.
> > > Hallo.
> > >
> > > Kann mir jemand sagen, was ich hier machen muss?
> Habe
> > > gerade das Internet durchsucht aber ich finde
> irgendwie
> > > nichts passendes, was mir hier weiterhilft.
> >
> > Vllt findest du was in deiner Vorlesungsmitschrift?
> >
> > Wieso bekommt ihr immer Aufgaben, von denen du noch nie
> > vorher was gesehen hast? Hat eure Uni ein ganz besonderes
> > Lernkonzept?
> >
> > In a) gilt es jeweils die multiplikativ Inversen von 13 zu
> > bestimmen mod 23, mod 53 und mod 89.
> >
> > Schaue dir in diesem Zusammenhang mal den Euklidischen
> > Algorithmus an ... 

>
>

> Danke für die Information.

>
>

> > Hast du gesehen, dass alle Moduln prim sind?
> >
> > Bei c)
> >
> > Erste Aufgabe: Was bedeutet denn [mm]53\equiv x \ \mod(3)[/mm]?
> >

>

> > Wenn dir das nicht klar ist, kannst du die Aufgaben nicht
> > lösen ...
> >
> > Also mache dich in deiner VL-Mitschrift schlau. Ohne
> > Definition bzw. Verständnis des [mm]\equiv[/mm] wird das sonst nix
> > ...
> >
> >
> > >
> > >
> > > Danke schonmal.
> >
> > Gruß
> >
> > schachuzipus

>
>

> In meinen Skripten steht leider nichts zu diesem Thema..

>

> Aber ich habe ein paar schöne Definitionen gefunden.

>

> 2 Zahlen a,b [mm]\in \IZ[/mm] heißen kongruent modulo m wenn gilt:

>

> a [mm]\equiv[/mm] b mod m.

Das ist nur eine Schrweibweise ...

>

> Das heißt, beide Zahlen lassen durch teilen von m
> denselben Rest.

[ok] Aha!

>

> Desweiteren ist a [mm]\equiv[/mm] b mod m [mm]\gdw[/mm] (a-b) = 0

>
>

> Also muss ich quasi ein x suchen aus dem gegebenen
> Definitionsbereich.

>
>

> [mm]5^3[/mm] ≡ x mod3, 0 ≤ x ≤ 2

>

> [mm]\gdw 5^3[/mm] - x = 0 mod 3
> [mm]\gdw[/mm] 125-x mod 3 = 0

>

> und mit x=2 wäre

>

> 125-2 mod 3 = 0 [mm]\gdw[/mm] 123 mod 3 = 0

>

> Also ist das gesuchte x =2.

Jo, hier kannst du das per Hand ausrechnen.

>

> Jetzt habe ich aber noch eine Verständnisfrage:

>
>

> 9^11 ≡ x mod11, 0 ≤ x ≤ 10

>

> 9^11 = 31381059609

>

> Gibt es hier irgendeinen Kniff, diese Aufgabe zu
> vereinfachen?

Na klar, es gibt ja Reihenweise Rechenregeln für die Kongruenzrechnung ...

Kennst du die Eulersche Phi-Funktion? Weißt du, was [mm] $\varphi(11)$ [/mm] ist?

Hier auch ein Stichwort: Satz von Fermat/Euler ("kleiner Fermat")

Dann ist es ganz einfach mit [mm] $9^{11}=9^{10}\cdot{}9$ [/mm] und den "basic" Rechenregeln für Kongruenzen...

Gruß

schachuzipus

Bezug
                                
Bezug
mod: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 17:38 Di 26.11.2013
Autor: kRAITOS


> Hallo nochmal,
>  
>
> > > Hallo,
>  > >

>  > > > b) Bestimmen Sie für p [mm]\in[/mm] {23,53,89} die ganze

> Zahl x
>  > > [mm]\in[/mm]

>  > > > {0, ..., p−1}, für die

>  > > > 13 · x ≡ 1 mod p

>  > > > gilt.

>  > > >

>  > > >

>  > > > c) Bestimmen Sie jeweils die ganze Zahl x [mm]\in \IZ[/mm]

> mit
>  > > den

>  > > > geforderten Eigenschaften:

>  > > >

>  > > > • 53 ≡ x mod3, 0 ≤ x ≤ 2,

>  > > > • 45 ≡ x mod5, 0 ≤ x ≤ 4,

>  > > > • 117 ≡ x mod7, 0 ≤ x ≤ 6,

>  > > > • 911 ≡ x mod11, 0 ≤ x ≤ 10,

>  > > > • 212 ≡ x mod13, 0 ≤ x ≤ 12.

>  > > > Hallo.

>  > > >

>  > > > Kann mir jemand sagen, was ich hier machen muss?

>  > Habe

>  > > > gerade das Internet durchsucht aber ich finde

>  > irgendwie

>  > > > nichts passendes, was mir hier weiterhilft.

>  > >

>  > > Vllt findest du was in deiner Vorlesungsmitschrift?

>  > >

>  > > Wieso bekommt ihr immer Aufgaben, von denen du noch

> nie
>  > > vorher was gesehen hast? Hat eure Uni ein ganz

> besonderes
>  > > Lernkonzept?

>  > >

>  > > In a) gilt es jeweils die multiplikativ Inversen von

> 13 zu
>  > > bestimmen mod 23, mod 53 und mod 89.

>  > >

>  > > Schaue dir in diesem Zusammenhang mal den

> Euklidischen
>  > > Algorithmus an ... 

>  >
>  >
>  > Danke für die Information.

>  >
>  >
>  > > Hast du gesehen, dass alle Moduln prim sind?

>  > >

>  > > Bei c)

>  > >

>  > > Erste Aufgabe: Was bedeutet denn [mm]53\equiv x \ \mod(3)[/mm]?

>  
> > >
>  >
>  > > Wenn dir das nicht klar ist, kannst du die Aufgaben

> nicht
>  > > lösen ...

>  > >

>  > > Also mache dich in deiner VL-Mitschrift schlau. Ohne

>  > > Definition bzw. Verständnis des [mm]\equiv[/mm] wird das sonst

> nix
>  > > ...

>  > >

>  > >

>  > > >

>  > > >

>  > > > Danke schonmal.

>  > >

>  > > Gruß

>  > >

>  > > schachuzipus

>  >
>  >
>  > In meinen Skripten steht leider nichts zu diesem

> Thema..
>  >
>  > Aber ich habe ein paar schöne Definitionen gefunden.

>  >
>  > 2 Zahlen a,b [mm]\in \IZ[/mm] heißen kongruent modulo m wenn

> gilt:
>  >
>  > a [mm]\equiv[/mm] b mod m.

>  
> Das ist nur eine Schrweibweise ...
>  
> >
>  > Das heißt, beide Zahlen lassen durch teilen von m

>  > denselben Rest.

>  
> [ok] Aha!
>  
> >
>  > Desweiteren ist a [mm]\equiv[/mm] b mod m [mm]\gdw[/mm] (a-b) = 0

>  >
>  >
>  > Also muss ich quasi ein x suchen aus dem gegebenen

>  > Definitionsbereich.

>  >
>  >
>  > [mm]5^3[/mm] ≡ x mod3, 0 ≤ x ≤ 2

>  >
>  > [mm]\gdw 5^3[/mm] - x = 0 mod 3

>  > [mm]\gdw[/mm] 125-x mod 3 = 0

>  >
>  > und mit x=2 wäre

>  >
>  > 125-2 mod 3 = 0 [mm]\gdw[/mm] 123 mod 3 = 0

>  >
>  > Also ist das gesuchte x =2.

>  
> Jo, hier kannst du das per Hand ausrechnen.
>  
> >
>  > Jetzt habe ich aber noch eine Verständnisfrage:

>  >
>  >
>  > 9^11 ≡ x mod11, 0 ≤ x ≤ 10

>  >
>  > 9^11 = 31381059609

>  >
>  > Gibt es hier irgendeinen Kniff, diese Aufgabe zu

>  > vereinfachen?

>  
> Na klar, es gibt ja Reihenweise Rechenregeln für die
> Kongruenzrechnung ...
>  
> Kennst du die Eulersche Phi-Funktion? Weißt du, was
> [mm]\varphi(11)[/mm] ist?

Noch nicht aber das kann man ja schnell nachholen. Auf jeden Fall habe ich nun ruckzuck auch die anderen Aufgaben gelöst. Danke dir.

>  
> Hier auch ein Stichwort: Satz von Fermat/Euler ("kleiner
> Fermat")
>  
> Dann ist es ganz einfach mit [mm]9^{11}=9^{10}\cdot{}9[/mm] und den
> "basic" Rechenregeln für Kongruenzen...
>  
> Gruß
>  
> schachuzipus


Bezug
                                
Bezug
mod: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 20:10 Do 28.11.2013
Autor: kRAITOS


>  > Jetzt habe ich aber noch eine Verständnisfrage:

>  >
>  >
>  > 9^11 ≡ x mod11, 0 ≤ x ≤ 10

>  >
>  > 9^11 = 31381059609

>  >
>  > Gibt es hier irgendeinen Kniff, diese Aufgabe zu

>  > vereinfachen?

>  
> Na klar, es gibt ja Reihenweise Rechenregeln für die
> Kongruenzrechnung ...
>  
> Kennst du die Eulersche Phi-Funktion? Weißt du, was
> [mm]\varphi(11)[/mm] ist?
>  
> Hier auch ein Stichwort: Satz von Fermat/Euler ("kleiner
> Fermat")
>  
> Dann ist es ganz einfach mit [mm]9^{11}=9^{10}\cdot{}9[/mm] und den
> "basic" Rechenregeln für Kongruenzen...
>  
> Gruß
>  
> schachuzipus


Also verstanden habe ich das ganze... Nur hat 9^11 [mm] \equiv [/mm] x mod 11 2 Lösungen...

Ich habe das wie folgt gemacht: (Natürlich vorher geraten. ;-) )


[mm] 9^1^1 \equiv 9^1^0 [/mm] * 9 [mm] \equiv (-2)^1^0 [/mm] * (-2) [mm] \equiv (4)^5 [/mm] * (-2) [mm] \equiv 4^4 [/mm] * (-8) [mm] \equiv 16^2 [/mm] * 3 [mm] \equiv 5^2 [/mm] * 3 [mm] \equiv [/mm] 25 * 3 [mm] \equiv [/mm] 3*3 [mm] \equiv [/mm] 9 mod 11

Durch vorheriges Raten aber kam auch 1 als Lösung. Meine Frage daher: Wie würde ich jetzt sehen, dass eine Kongruenz mehrere Lösungen hat bzw wie würde ich hier auf gerade eben 1 als Lösung kommen?

Bezug
                                        
Bezug
mod: Antwort
Status: (Antwort) fertig Status 
Datum: 06:42 Fr 29.11.2013
Autor: angela.h.b.


> Also verstanden habe ich das ganze... Nur hat 9^11 [mm]\equiv[/mm] x
> mod 11 2 Lösungen...

Hallo,

es kann keine zwei verschiedenen Lösungen zwischen 0 und 10 geben. Das würde ja bedeuten, daß man bei Division durch 11 zwei verschiedene Ergebnisse bekommt.

>

> Ich habe das wie folgt gemacht: (Natürlich vorher geraten.
> ;-) )

>
>

> [mm]9^1^1 \equiv 9^1^0[/mm] * 9 [mm]\equiv (-2)^1^0[/mm] * (-2) [mm]\equiv (4)^5[/mm]
> * (-2) [mm]\equiv 4^4[/mm] * (-8) [mm]\equiv 16^2[/mm] * 3 [mm]\equiv 5^2[/mm] * 3
> [mm]\equiv[/mm] 25 * 3 [mm]\equiv[/mm] 3*3 [mm]\equiv[/mm] 9 mod 11

Das sieht richtig aus.
>

> Durch vorheriges Raten aber kam auch 1 als Lösung.

Ich frage mich, wie man bei diesen Aufgaben Ergebnisse erraten kann.
Wie dem auch sei: 1 ist falsch.


Meine

> Frage daher: Wie würde ich jetzt sehen, dass eine
> Kongruenz mehrere Lösungen hat bzw wie würde ich hier auf
> gerade eben 1 als Lösung kommen?

Auf die 1kommt man gar nicht, und Kongruenzen der Gestalt

a=x mod b haben genau eine Lösung [mm] 0\le x\le [/mm] b-1.

LG Angela

Bezug
                                                
Bezug
mod: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 13:00 Fr 29.11.2013
Autor: kRAITOS

Hallo.

Na wir wissen ja, dass a [mm] \equiv [/mm] b mod m [mm] \gdw [/mm] a-b mod m = 0

Würde man jetzt einsetzen, dann ist [mm] 9^1^1 [/mm] - 1 mod [mm] 11\equiv [/mm] 0 mod 11. Damit wäre diese Bedingung erfüllt.

Aber okay, mir reicht schon die Aussage, dass diese Aufgaben nur eine Lösung besitzen. :-)

Danke.


Bezug
                                                        
Bezug
mod: Antwort
Status: (Antwort) fertig Status 
Datum: 13:25 Fr 29.11.2013
Autor: angela.h.b.


> Hallo.

>

> Na wir wissen ja, dass a [mm]\equiv[/mm] b mod m [mm]\gdw[/mm] a-b mod m = 0

Hallo,

wenn a und b denselben Rest modulo m lassen, ist ihre Differenz ein Vielfaches von m, läßt also bei Division durch m den Rest 0.

>

> Würde man jetzt einsetzen, dann ist [mm]9^1^1[/mm] - 1 mod [mm]11\equiv[/mm]
> 0 mod 11. Damit wäre diese Bedingung erfüllt.

???
Du setzt dabei aber voraus, daß 9^11 bei Division durch 11 den Rest 1 läßt.
Das ist aber nicht der Fall!
Es bleibt der Rest 9.

Wie kommst Du bloß auf 1? Hmm - hast Du vielleicht den kl. Satz von Fermat falsch im Kopf?

Der kl. Fermat sagt:
wenn p eine Primzahl ist, ist [mm] a^{p-1}\equiv [/mm] 1 mod p ,
oder anders ausgedrückt
[mm] a^p\equiv [/mm] a mod p.

LG Angela


>

> Aber okay, mir reicht schon die Aussage, dass diese
> Aufgaben nur eine Lösung besitzen. :-)

>

> Danke.

>

Bezug
                                                                
Bezug
mod: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 14:02 Fr 29.11.2013
Autor: kRAITOS


> > Hallo.
>  >
>  > Na wir wissen ja, dass a [mm]\equiv[/mm] b mod m [mm]\gdw[/mm] a-b mod m =

> 0
>  
> Hallo,
>  
> wenn a und b denselben Rest modulo m lassen, ist ihre
> Differenz ein Vielfaches von m, läßt also bei Division
> durch m den Rest 0.
>  
> >
>  > Würde man jetzt einsetzen, dann ist [mm]9^1^1[/mm] - 1 mod

> [mm]11\equiv[/mm]
>  > 0 mod 11. Damit wäre diese Bedingung erfüllt.

>  
> ???
>  Du setzt dabei aber voraus, daß 9^11 bei Division durch
> 11 den Rest 1 läßt.
>  Das ist aber nicht der Fall!
>  Es bleibt der Rest 9.
>  
> Wie kommst Du bloß auf 1? Hmm - hast Du vielleicht den kl.
> Satz von Fermat falsch im Kopf?
>  

Ich hatte ihn gar nicht im Kopf. Aber hab ihn mir gerad angeshaut und nun schäme ich mich ja fast für meinen langen Rechnungsweg.

Das geht ja auch viel Kürzer:

[mm] 9^1^1 \equiv 9^1^0 [/mm] * 9 [mm] \equiv [/mm] 1*9 [mm] \equiv [/mm] 9 mod 11


Danke für diese Einsicht. :D

> Der kl. Fermat sagt:
>  wenn p eine Primzahl ist, ist [mm]a^{p-1}\equiv[/mm] 1 mod p ,
>  oder anders ausgedrückt
>  [mm]a^p\equiv[/mm] a mod p.
>  
> LG Angela
>  
>
> >
>  > Aber okay, mir reicht schon die Aussage, dass diese

>  > Aufgaben nur eine Lösung besitzen. :-)

>  >
>  > Danke.

>  >


Bezug
                
Bezug
mod: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 17:47 Do 28.11.2013
Autor: kRAITOS


> Hallo,
>  
> > b) Bestimmen Sie für p [mm]\in[/mm] {23,53,89} die ganze Zahl x
> [mm]\in[/mm]
>  > {0, ..., p−1}, für die

>  > 13 · x ≡ 1 mod p

>  > gilt.

>  >
>  >
>  > c) Bestimmen Sie jeweils die ganze Zahl x [mm]\in \IZ[/mm] mit

> den
>  > geforderten Eigenschaften:

>  >
>  > • 53 ≡ x mod3, 0 ≤ x ≤ 2,

>  > • 45 ≡ x mod5, 0 ≤ x ≤ 4,

>  > • 117 ≡ x mod7, 0 ≤ x ≤ 6,

>  > • 911 ≡ x mod11, 0 ≤ x ≤ 10,

>  > • 212 ≡ x mod13, 0 ≤ x ≤ 12.

>  > Hallo.

>  >
>  > Kann mir jemand sagen, was ich hier machen muss? Habe

>  > gerade das Internet durchsucht aber ich finde irgendwie

>  > nichts passendes, was mir hier weiterhilft.

>  
> Vllt findest du was in deiner Vorlesungsmitschrift?
>  
> Wieso bekommt ihr immer Aufgaben, von denen du noch nie
> vorher was gesehen hast? Hat eure Uni ein ganz besonderes
> Lernkonzept?
>  
> In a) gilt es jeweils die multiplikativ Inversen von 13 zu
> bestimmen mod 23, mod 53 und mod 89.
>  
> Schaue dir in diesem Zusammenhang mal den Euklidischen
> Algorithmus an ... 

Hallo. Ich nochmal.

Ich verstehe nicht ganz den Zusammenhang vom euklidischen Algorithmus und Aufgabenteil b.

Vllt mag jemand kurz Licht reinbringen?


>  
> Hast du gesehen, dass alle Moduln prim sind?
>  
> Bei c)
>  
> Erste Aufgabe: Was bedeutet denn [mm]53\equiv x \ \mod(3)[/mm]?
>  
> Wenn dir das nicht klar ist, kannst du die Aufgaben nicht
> lösen ...
>  
> Also mache dich in deiner VL-Mitschrift schlau. Ohne
> Definition bzw. Verständnis des [mm]\equiv[/mm] wird das sonst nix
> ...
>  
>
> >
>  >
>  > Danke schonmal.

>  
> Gruß
>  
> schachuzipus


Bezug
                        
Bezug
mod: Antwort
Status: (Antwort) fertig Status 
Datum: 17:53 Do 28.11.2013
Autor: schachuzipus

Hallo nochmal,

kannst du bitte mal vernünftig zitieren ...

[motz]


> > > b) Bestimmen Sie für p [mm]\in[/mm] {23,53,89} die ganze Zahl x
> > [mm]\in[/mm]
> > > {0, ..., p−1}, für die
> > > 13 · x ≡ 1 mod p
> > > gilt.

> Hallo. Ich nochmal.

>

> Ich verstehe nicht ganz den Zusammenhang vom euklidischen
> Algorithmus und Aufgabenteil b.

>

> Vllt mag jemand kurz Licht reinbringen?

>

zu p=23:

Berechne [mm]\ggT(13,23)=1[/mm] mit dem Euklidischen Algorithmus.

Dann von unten nach oben rückwärts rechnen und 1, also den [mm]\ggT(13,23)[/mm] als Linearkombination von 13 und 23 darstellen.

Also so:

[mm]1=a\cdot{}13+b\cdot{}23[/mm] - die [mm]a,b\in\IZ[/mm] berechne nun erstmal ...

Gruß

schachuzipus

Bezug
                                
Bezug
mod: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 19:43 Do 28.11.2013
Autor: kRAITOS


> Hallo nochmal,
>  
> kannst du bitte mal vernünftig zitieren ...
>  
> [motz]
>  
>
> > > > b) Bestimmen Sie für p [mm]\in[/mm] {23,53,89} die ganze Zahl x
>  > > [mm]\in[/mm]

>  > > > {0, ..., p−1}, für die

>  > > > 13 · x ≡ 1 mod p

>  > > > gilt.

>  
> > Hallo. Ich nochmal.
>  >
>  > Ich verstehe nicht ganz den Zusammenhang vom

> euklidischen
>  > Algorithmus und Aufgabenteil b.

>  >
>  > Vllt mag jemand kurz Licht reinbringen?

>  >
>  
> zu p=23:
>  
> Berechne [mm]\ggT(13,23)=1[/mm] mit dem Euklidischen Algorithmus.
>  
> Dann von unten nach oben rückwärts rechnen und 1, also
> den [mm]\ggT(13,23)[/mm] als Linearkombination von 13 und 23
> darstellen.
>  
> Also so:
>  
> [mm]1=a\cdot{}13+b\cdot{}23[/mm] - die [mm]a,b\in\IZ[/mm] berechne nun
> erstmal ...
>  

Da kam ich auf a=-7 und b = 4.

Muss ich jetzt das a nehmen, um die Kongruenz für

13 · x ≡ 1 mod 23

zu zeigen? Das würde ja nicht gehen, da das x laut Aufgabe ja [mm] \in \{0, ..., p-1\} [/mm] sein soll.


> Gruß
>  
> schachuzipus

Bezug
                                        
Bezug
mod: Antwort
Status: (Antwort) fertig Status 
Datum: 06:48 Fr 29.11.2013
Autor: angela.h.b.


> > Also so:
> >
> > [mm]1=a\cdot{}13+b\cdot{}23[/mm] - die [mm]a,b\in\IZ[/mm] berechne nun
> > erstmal ...
> >

>

> Da kam ich auf a=-7 und b = 4.

>

> Muss ich jetzt das a nehmen, um die Kongruenz für

>

> 13 · x ≡ 1 mod 23

>

> zu zeigen?

Hallo,

dann wäre die Aufgabe ohne die Einschränkung [mm] x\in \{0,1,...,22\} [/mm] auf jeden Fall richtig gelöst.

> Das würde ja nicht gehen, da das x laut Aufgabe
> ja [mm]\in \{0, ..., p-1\}[/mm] sein soll.

Ja, das stimmt.

Es ist [mm] -7\equiv [/mm] 16 mod 23,

und mit x=16 ist die gesuchte Lösung gefunden.

(Überzeuge Dich davon, daß es eine Lösung ist.)

LG Angela
>
>

> > Gruß
> >
> > schachuzipus


Bezug
                                                
Bezug
mod: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 16:20 Fr 29.11.2013
Autor: kRAITOS


>
> > > Also so:
>  > >

>  > > [mm]1=a\cdot{}13+b\cdot{}23[/mm] - die [mm]a,b\in\IZ[/mm] berechne nun

>  > > erstmal ...

>  > >

>  >
>  > Da kam ich auf a=-7 und b = 4.

>  >
>  > Muss ich jetzt das a nehmen, um die Kongruenz für

>  >
>  > 13 · x ≡ 1 mod 23

>  >
>  > zu zeigen?

>  
> Hallo,
>  
> dann wäre die Aufgabe ohne die Einschränkung [mm]x\in \{0,1,...,22\}[/mm]
> auf jeden Fall richtig gelöst.
>  
> > Das würde ja nicht gehen, da das x laut Aufgabe
>  > ja [mm]\in \{0, ..., p-1\}[/mm] sein soll.

>  
> Ja, das stimmt.
>  
> Es ist [mm]-7\equiv[/mm] 16 mod 23,
>  
> und mit x=16 ist die gesuchte Lösung gefunden.
>  
> (Überzeuge Dich davon, daß es eine Lösung ist.)

-7 - 16 [mm] \equiv [/mm] -23 = 0 mod 23

Das ist klar. Aber wie kommt man auf die 16?


>  
> LG Angela
>  >
>  >
>  > > Gruß

>  > >

>  > > schachuzipus


Bezug
                                                        
Bezug
mod: Antwort
Status: (Antwort) fertig Status 
Datum: 16:33 Fr 29.11.2013
Autor: abakus


> >
> > > > Also so:
> > > >
> > > > [mm]1=a\cdot{}13+b\cdot{}23[/mm] - die [mm]a,b\in\IZ[/mm] berechne
> nun
> > > > erstmal ...
> > > >
> > >
> > > Da kam ich auf a=-7 und b = 4.
> > >
> > > Muss ich jetzt das a nehmen, um die Kongruenz für
> > >
> > > 13 · x ≡ 1 mod 23
> > >
> > > zu zeigen?
> >
> > Hallo,
> >
> > dann wäre die Aufgabe ohne die Einschränkung [mm]x\in \{0,1,...,22\}[/mm]
> > auf jeden Fall richtig gelöst.
> >
> > > Das würde ja nicht gehen, da das x laut Aufgabe
> > > ja [mm]\in \{0, ..., p-1\}[/mm] sein soll.
> >
> > Ja, das stimmt.
> >
> > Es ist [mm]-7\equiv[/mm] 16 mod 23,
> >
> > und mit x=16 ist die gesuchte Lösung gefunden.
> >
> > (Überzeuge Dich davon, daß es eine Lösung ist.)

>

> -7 - 16 [mm]\equiv[/mm] -23 = 0 mod 23

>

> Das ist klar. Aber wie kommt man auf die 16?

Hallo,
die Zahlen
..., -53, -30, -7, 16, 39,...
sind zueinander kongruent nach dem Modul 23, weil 
1) die Differenz von zwei dieser Zahlen durch 23 teilbar ist
2) sie alle den selben Rest (nämlich 16) bei Teilung durch 23 lassen, denn es sind die Zahlen
..., (-3)*23+16, (-2)*23+16, (-1)*23+16, 0*23+16, 1*23+16,...

Gruß Abakus
>
>

> >
> > LG Angela
> > >
> > >
> > > > Gruß
> > > >
> > > > schachuzipus

>

Bezug
                                                                
Bezug
mod: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 17:35 Fr 29.11.2013
Autor: kRAITOS

Okay.

Also ich errechne mir x und y und davon brauche ich dann nur x.


Das setze ich ein in

13*x [mm] \equiv [/mm] 1 mod 13    mit x = -7
13*x [mm] \equiv [/mm] 1 mod 53    mit x = -4
13*x [mm] \equiv [/mm] 1 mod 89    mit x = -41


und dann schaue ich, zu welcher positiven Zahl das x kongruent ist, da die Menge, aus der das x kommen soll, ja positiv ist.

also ist -7 [mm] \equiv [/mm] 16, weil -7 +23 = 16
-4 [mm] \equiv [/mm] 49
-41 [mm] \equiv [/mm] 48




Bezug
                                                                        
Bezug
mod: Antwort
Status: (Antwort) fertig Status 
Datum: 20:05 Fr 29.11.2013
Autor: angela.h.b.


> Okay.

>

> Also ich errechne mir x und y und davon brauche ich dann
> nur x.

Ja.

>
>

> Das setze ich ein in

>

> 13*x [mm]\equiv[/mm] 1 mod 13 mit x = -7
> 13*x [mm]\equiv[/mm] 1 mod 53 mit x = -4
> 13*x [mm]\equiv[/mm] 1 mod 89 mit x = -41

>
>

> und dann schaue ich, zu welcher positiven Zahl das x
> kongruent ist, da die Menge, aus der das x kommen soll, ja
> positiv ist.

>

> also ist -7 [mm]\equiv[/mm] 16, weil -7 +23 = 16
> -4 [mm]\equiv[/mm] 49
> -41 [mm]\equiv[/mm] 48

Genau.

LG Angela
>
>
>

Bezug
                                                        
Bezug
mod: Antwort
Status: (Antwort) fertig Status 
Datum: 16:40 Fr 29.11.2013
Autor: leduart

Hallo
-7=0+(-7)=23-7=16
immer_ -a mod p= p-amod p
Gruß leduart

Bezug
                                                        
Bezug
mod: Antwort
Status: (Antwort) fertig Status 
Datum: 16:44 Fr 29.11.2013
Autor: angela.h.b.


> > Es ist [mm]-7\equiv[/mm] 16 mod 23,
> >
> > und mit x=16 ist die gesuchte Lösung gefunden.
> >
> > (Überzeuge Dich davon, daß es eine Lösung ist.)

>

> -7 - 16 [mm]\equiv[/mm] -23 = 0 mod 23

>

> Das ist klar. Aber wie kommt man auf die 16?

Hallo,

lies -7 als "das Inverse der 7 bzgl der Addition modulo 23".

LG Angela

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


^ Seitenanfang ^
www.vorhilfe.de