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

Modulo: Lösung
Status: (Frage) beantwortet Status 
Datum: 15:20 So 05.08.2012
Autor: AntonK

Aufgabe
3x=1 mod 11

Hallo Leute,

und zwar sollte ich in der letzten Klausur dafür eine mögliche Lösung für x angeben und habe x=-4 gewählt, leider war dies falsch, verstehe leider nicht warum, eine mögliche Lösung wäre einfach nur 4 gewesen, wo ist mein Denkfehler?

Bei x=-4 habe ich mir gedacht:

3*(-4)=-12

Bis zur -11 fehlt also nur noch die Eins, weil -11 ja zu mod 11 gehört. Deswegen -12= 1 mod 11.

Habe mir das immer so klar gemacht, wir hatten auch mal ein Beispiel mit:

9=1 mod 4

Weil 2*4=8 und eben zur 9 noch Rest 1 fehlt. Das ist doch analog zu oben oder? Naja gut, mein Prof hat versucht es mir zu erklären, warum es nicht so ist, aber habe ich nicht verstanden, könnte mir das jemand erklären? Und auch bitte eine Methode zeigen, wie ich sowas ausrechnen kann? Meine ist ja anscheinend falsch.

Danke schonmal!

        
Bezug
Modulo: Antwort
Status: (Antwort) fertig Status 
Datum: 15:51 So 05.08.2012
Autor: felixf

Moin!

> 3x=1 mod 11
>  Hallo Leute,
>  
> und zwar sollte ich in der letzten Klausur dafür eine
> mögliche Lösung für x angeben und habe x=-4 gewählt,
> leider war dies falsch, verstehe leider nicht warum, eine
> mögliche Lösung wäre einfach nur 4 gewesen, wo ist mein
> Denkfehler?
>  
> Bei x=-4 habe ich mir gedacht:
>  
> 3*(-4)=-12
>  
> Bis zur -11 fehlt also nur noch die Eins, weil -11 ja zu
> mod 11 gehört. Deswegen -12= 1 mod 11.

Das macht keinen Sinn so, und hat auch nicht viel mit dem zu tun was du unten tust:

> Habe mir das immer so klar gemacht, wir hatten auch mal ein
> Beispiel mit:
>  
> 9=1 mod 4
>  
> Weil 2*4=8 und eben zur 9 noch Rest 1 fehlt.

Das ist korrekt.

> Das ist doch analog zu oben oder?

Nein.

Du musst du $-12 = -4 [mm] \cdot [/mm] 3$ ein Vielfaches von 11 addieren. Etwa $-12 + 11 = -1$, $-12 + 2 [mm] \cdot [/mm] 11 = 10$, ...

Wie du schnell sehen kannst, kommt da niemals 1 heraus, sondern nur -1 (und andere Zahlen, die kongruent zu -1 bzw. 10 modulo 11 sind).

LG Felix


Bezug
                
Bezug
Modulo: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 16:09 So 05.08.2012
Autor: AntonK

Hm, ok, das heißt die mit dem addieren ist die beste Methode? Gut nehme ich mal so hin.

Wir hatten noch eine Aufgabe und zwar hatten wir:

[mm] $2^{10}=1 [/mm] mod 11$

Wie kann man sowas beweisen? Ich bin hergegangen und habe gesagt:

[mm] $2^{10}=1024$ [/mm] und $11*93=1023$, deswegen 1 mod 11. Gibt es da eine bessere Methode, als einfach auszuprobieren? Wir dürfen nämlich keinen Taschenrechner benutzen.

Wir sollten nämlich auch ein y bestimmen für:

[mm] $2^{111111}=y [/mm] mod 11$ Wobei [mm] 0\le y\le10 [/mm] war.

Wie würde man da vorgehen?

Bezug
                        
Bezug
Modulo: Antwort
Status: (Antwort) fertig Status 
Datum: 16:17 So 05.08.2012
Autor: felixf

Moin!

> Hm, ok, das heißt die mit dem addieren ist die beste
> Methode? Gut nehme ich mal so hin.
>  
> Wir hatten noch eine Aufgabe und zwar hatten wir:
>  
> [mm]2^{10}=1 mod 11[/mm]
>  
> Wie kann man sowas beweisen? Ich bin hergegangen und habe
> gesagt:
>  
> [mm]2^{10}=1024[/mm] und [mm]11*93=1023[/mm], deswegen 1 mod 11. Gibt es da
> eine bessere Methode, als einfach auszuprobieren? Wir
> dürfen nämlich keinen Taschenrechner benutzen.

Klar, du kannst den kleinen Satz von Fermat verwenden (bzw. desssen Bruder, den Satz von Euler): da $11$ eine Primzahl ist, gilt [mm] $a^{11 - 1} \equiv [/mm] 1 [mm] \pmod{11}$ [/mm] fuer jede Zahl $a$, die nicht durch 11 teilbar ist. $a = 2$ ist eine solche.

> Wir sollten nämlich auch ein y bestimmen für:
>  
> [mm]2^{111111}=y mod 11[/mm] Wobei [mm]0\le y\le10[/mm] war.
>  
> Wie würde man da vorgehen?

Du weisst ja [mm] $2^{10} \equiv [/mm] 1 [mm] \pmod{11}$. [/mm] Damit ist [mm] $2^{111111} [/mm] = [mm] 2^{10 \cdot a + b} \equiv (2^{10})^a \cdot 2^b \equiv 1^a \cdot 2^b [/mm] = [mm] 2^b \pmod{11}$, [/mm] wobei du $a$ und $b$ durch Division mit Rest $111111 = 10 [mm] \cdot [/mm] a + b$ bekommst (mit $0 [mm] \le [/mm] b  < 10$). Schliesslich musst du noch [mm] $2^b$ [/mm] bestimmen, was hier allerdings sehr, sehr einfach ist.

LG Felix


Bezug
                                
Bezug
Modulo: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 16:28 So 05.08.2012
Autor: AntonK

[mm] 2^b=1 [/mm] also ist b=0 oder? Das ist jetzt mehr oder weniger vermutet, verstehe aber rechnerisch nicht wieso dies so sein muss, der Groschen ist noch nicht ganz gefallen.

Bezug
                                        
Bezug
Modulo: Antwort
Status: (Antwort) fertig Status 
Datum: 16:41 So 05.08.2012
Autor: M.Rex

Hallo

Es gilt ja:

$ [mm] a^{n+1}=a\cdot a^{n}\Leftrightarrow\frac{a^{n+1}}{a^{n}}=a [/mm] $

Also:
[mm] $\frac{a^{0+1}}{a^{0}}=a$ [/mm]
[mm] $\Leftrightarrow \frac{a}{a^{0}}=a$ [/mm]
[mm] $\Leftrightarrow \frac{1}{a^{0}}=1$ [/mm]

Und das geht nur, wenn [mm] a^{0}=1 [/mm] ist.

Für n=0 soll das ganze nun auch noch gelten, das erspart für einige Induktionsbeweise eine Menge hässlicher Fallunterscheidungen, ja sogar [mm] 0^{0} [/mm] wird üblicherweise als 1 definiert, das macht am wenigsten "Komplikationen".

Marius


Bezug
                                                
Bezug
Modulo: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 17:19 So 05.08.2012
Autor: AntonK

Ich verstehe leider nicht, was dies damit zu tun hat.

Bezug
                                                        
Bezug
Modulo: Antwort
Status: (Antwort) fertig Status 
Datum: 17:33 So 05.08.2012
Autor: M.Rex


> Ich verstehe leider nicht, was dies damit zu tun hat.

Wu wolltest doch wissen, warum gilt: [mm]\forall a:a^{0}=1[/mm]

Marius


Bezug
                                                                
Bezug
Modulo: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 21:32 So 05.08.2012
Autor: AntonK

Ja, ok, danke!

Bezug
                                        
Bezug
Modulo: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 17:03 So 05.08.2012
Autor: felixf

Moin!

> [mm]2^b=1[/mm] also ist b=0 oder? Das ist jetzt mehr oder weniger
> vermutet, verstehe aber rechnerisch nicht wieso dies so
> sein muss, der Groschen ist noch nicht ganz gefallen.

Koenntest du bitte sagen, was der Zusammenhang ist zwischen diesen zwei Saetzen und dem, was ich geschrieben hatte?

LG Felix


Bezug
                                                
Bezug
Modulo: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 17:17 So 05.08.2012
Autor: AntonK

$ [mm] 2^{111111} [/mm] = [mm] 2^{10 \cdot a + b} \equiv (2^{10})^a \cdot 2^b \equiv 1^a \cdot 2^b [/mm] = [mm] 2^b \pmod{11} [/mm] $

Ich kann ganz einfach mit dieser Rechnung nichts anfangen, mathematisch ist mir das klar, aber dieses [mm] $2^b$ [/mm] sagt mir nichts.Was konkret ist das? Ist das mein y oder was muss ich mir darunter vorstellen?

Bezug
                                                        
Bezug
Modulo: Antwort
Status: (Antwort) fertig Status 
Datum: 17:36 So 05.08.2012
Autor: felixf

Moin!

> [mm]2^{111111} = 2^{10 \cdot a + b} \equiv (2^{10})^a \cdot 2^b \equiv 1^a \cdot 2^b = 2^b \pmod{11}[/mm]
>  
> Ich kann ganz einfach mit dieser Rechnung nichts anfangen,
> mathematisch ist mir das klar, aber dieses [mm]2^b[/mm] sagt mir
> nichts.Was konkret ist das? Ist das mein y oder was muss
> ich mir darunter vorstellen?

Das ist (modulo 11) gleich deinem $y$.

Du musst jetzt $a$ und $b$ bestimmen, damit $111111 = 10 [mm] \cdot [/mm] a + b$ mit $0 [mm] \le [/mm] b < 10$ ist.

Dann hast du einen konkreten Wert fuer $b$ und kannst $y$ damit bestimmen.

LG Felix


Bezug
                                                                
Bezug
Modulo: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 21:36 So 05.08.2012
Autor: AntonK

Wenn ich z.B. nach auf auflöse:

[mm] \bruch{111111-b}{10}=a [/mm]

Ich würde dann b=1 wählen und hätte dann a=11111

Das kann aber so nicht sein oder? a muss doch durch 11 teilbar sein oder sehe ich das falsch?

Bezug
                                                                        
Bezug
Modulo: Antwort
Status: (Antwort) fertig Status 
Datum: 22:04 So 05.08.2012
Autor: abakus


> Wenn ich z.B. nach auf auflöse:
>  
> [mm]\bruch{111111-b}{10}=a[/mm]
>  
> Ich würde dann b=1 wählen und hätte dann a=11111
>  
> Das kann aber so nicht sein oder? a muss doch durch 11
> teilbar sein oder sehe ich das falsch?

Hallo,
gehen wir mal weniger theoretisch (ohne "a" und "b") heran.
Du weißt inzwischen, dass [mm]2^{10}\equiv 1 mod 11[/mm] gilt.
Diese Kongruenz kann man mit sich selbst multiplizieren.
Es gilt damit [mm]2^{10}*2^{10}\equiv 1*1 mod 11[/mm]
also [mm]2^{20}\equiv 1*mod 11[/mm].
Diese Kongruenz kann man wieder mit [mm]2^{10}\equiv 1 mod 11[/mm] multiplizieren und erhält
<span class="math">[mm]2^{30}\equiv 1*mod 11[/mm].
Wenn man das fortführt, erhält man
[mm]2^{10}\equiv 2^{20}\equiv2^{30}\equiv 2^{40}\cdots\equiv 2^{11110}\equiv1 mod 11[/mm]
Um auf den Exponenten 11111 zu kommen, muss man noch einmal mit 2 multiplizieren.
Man hat bisher
<span class="math">[mm] 2^{11110}\equiv1 mod 11[/mm]
und weiß, dass auch [mm] 2^{1}\equiv2mod 11[/mm] gilt.
Multiplikation der beiden letztgenannten Kongruenzen führt zu
[mm] 2^{11110}*2\equiv1*2 mod 11[/mm], also [mm] 2^{11111}\equiv2 mod 11[/mm].
Gruß Abakus




</span>
</span>






Bezug
                                                                                
Bezug
Modulo: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 23:34 So 05.08.2012
Autor: AntonK

Um ehrlich zu sein, so verstehe ich das. Aber der andere Ansatz bereitet mir immernoch Kopfschmerzen, wäre cool, wenn sich noch jemand zu meiner letzten Frage äußern könnte. Aber dir erstmal vielen Dank!

Bezug
                                                                        
Bezug
Modulo: Antwort
Status: (Antwort) fertig Status 
Datum: 03:44 Di 07.08.2012
Autor: reverend

Hallo AntonK,

> Wenn ich z.B. nach auf auflöse:
>  
> [mm]\bruch{111111-b}{10}=a[/mm]
>  
> Ich würde dann b=1 wählen und hätte dann a=11111
>  
> Das kann aber so nicht sein oder? a muss doch durch 11
> teilbar sein oder sehe ich das falsch?

Nein, a muss nicht durch 11 teilbar sein.
Hier geht es doch darum, sozusagen den größten Teil von 111111 zu eliminieren. Man weiß, dass [mm] 2^{10}\equiv 1\mod{11} [/mm] ist und "entfernt" soviele Zehner wie möglich, also tatsächlich a=11111.

Egal wie groß a ist, ist doch [mm] \left(2^{10}\right)^a\equiv 1\mod{11}. [/mm]

Deine Wahl von b=1 ist richtig, und die Lösung daher

[mm] 2^{111111}=\left(2^{10}\right)^{11111}*2^1\equiv 2\mod{11} [/mm]

Die Aufgaben mit riesigen Exponenten (auch in der Klausur) funktionieren im Prinzip alle so.

Grüße
reverend


Bezug
                                                                                
Bezug
Modulo: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 10:09 Di 07.08.2012
Autor: AntonK

Verstehe, danke!

Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Gruppe, Ring, Körper"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


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