Modulo < Gruppe, Ring, Körper < Algebra < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
Status: |
(Frage) beantwortet | Datum: | 15:20 So 05.08.2012 | Autor: | AntonK |
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!
|
|
|
|
Status: |
(Antwort) fertig | 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
|
|
|
|
|
Status: |
(Frage) beantwortet | 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?
|
|
|
|
|
Status: |
(Antwort) fertig | 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
|
|
|
|
|
Status: |
(Frage) beantwortet | 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.
|
|
|
|
|
Status: |
(Antwort) fertig | 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
|
|
|
|
|
Status: |
(Frage) beantwortet | Datum: | 17:19 So 05.08.2012 | Autor: | AntonK |
Ich verstehe leider nicht, was dies damit zu tun hat.
|
|
|
|
|
Status: |
(Antwort) fertig | 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
|
|
|
|
|
Status: |
(Mitteilung) Reaktion unnötig | Datum: | 21:32 So 05.08.2012 | Autor: | AntonK |
Ja, ok, danke!
|
|
|
|
|
Status: |
(Mitteilung) Reaktion unnötig | 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
|
|
|
|
|
Status: |
(Frage) beantwortet | 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?
|
|
|
|
|
Status: |
(Antwort) fertig | 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
|
|
|
|
|
Status: |
(Frage) beantwortet | 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?
|
|
|
|
|
Status: |
(Antwort) fertig | 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>
|
|
|
|
|
Status: |
(Mitteilung) Reaktion unnötig | 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!
|
|
|
|
|
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
|
|
|
|
|
Status: |
(Mitteilung) Reaktion unnötig | Datum: | 10:09 Di 07.08.2012 | Autor: | AntonK |
Verstehe, danke!
|
|
|
|