Diskrete Mathematik: Kleiner Satz von Fermat?

22.07.2012, 12:54

leon_20v

Auf diesen Beitrag antworten »

Diskrete Mathematik: Kleiner Satz von Fermat?

Meine Frage:
Hallo zusammen,

ich hoffe ich bin hier richtig, hab hier ne Aufgabe die ich in der Klausur können muss aber ich weiß garnicht nach was ich suchen soll und wie ich mir das Aneignen soll,

gegeben: p(x) = 1+x, q(x) = 2+x, im Z7[x] mod (x²+1)
a) Berechnen Sie das Produkt p(x) * q(x) (5P)
b) Z7[x] mod (x²+1), Wie viele Elemente hat der Körper? (2P)

Meine Ideen:
Restklassen, Endliche Körper...

22.07.2012, 13:23

Captain Kirk

Auf diesen Beitrag antworten »

Hallo,

nochmal zur Klarstellung für mich:
Z7 soll den Restklassenring/Körper mit 7 Elementen bezeichnen? (Also $\begin{eqnarray*} \mathbb Z/7\mathbb Z \end{eqnarray*}$ oder $\begin{eqnarray*} \mathbb F_7 \end{eqnarray*}$ )

Und p und q leben in $\begin{eqnarray*} \mathbb F_7[X]/(X^2+1) \end{eqnarray*}$ ?

a)Produkt ganz "normal" berechnen, dann modulo X²+1 betrachten.
b) Was für eine Dimension als Vektorraum hat der Körper (ist dir klar warum das einer ist?) über $\begin{eqnarray*} \mathbb F_7 \end{eqnarray*}$ ? Was sagt das über die Anzahl der Elemente aus?

Was mich jetzt noch interessieren würde: Wo siehst du hier eine Anwendung des kleinen Fermat?

22.07.2012, 16:16

Leon_20v

Auf diesen Beitrag antworten »

ach ich hab den Fermat noch nicht so richtig kapiert und ich hatte ne andere Aufgabe die so ähnlich aussah aber doch ganz anderst ist wo der Fermat benutzt wird.

Danke für deine Antwort, aber ich bin mir glaub noch nicht so ganz im klaren, was der unterschied zwischen Also $\begin{eqnarray*} \mathbb Z/7\mathbb Z \end{eqnarray*}$ oder $\begin{eqnarray*} \mathbb F_7 \end{eqnarray*}$ ist.

Ich hab mal die Aufgabe als Bild in den Anhang gepackt.

a) wenn ich das ganz normal berechne muss ich da nicht Z7 irgendwie beachten? Wir haben das mal im Z2 ohne anderes modulo gemacht da durften dann nur werte mit 0,1 drinn sein.

Wenn ich modulo X²+1 betrachte was bedeutet das dann für die Aufgabe? Modulo mit normalen zahlen ist mir klar, aber sobald da unbekannte vorkommen schalten mein Gehirn irgendwie auf dumm unglücklich

unglücklich

b) Leider nicht klar warum er ein Körper ist unglücklich

unglücklich

Ich geh gerade unser Skript durch, doch irgendwie steht da alles nur allgemein und Sätze die ich irgendwie nicht schaffe richtig anzuwenden unglücklich

unglücklich

22.07.2012, 16:42

Captain Kirk

Auf diesen Beitrag antworten »

Zitat:

aber ich bin mir glaub noch nicht so ganz im klaren, was der unterschied zwischen Also $\begin{eqnarray*} \mathbb Z/7\mathbb Z \end{eqnarray*}$ oder $\begin{eqnarray*} \mathbb F_7 \end{eqnarray*}$ ist.

Keiner, sind verschiedene Schreibweisen des selben. Mit $\begin{eqnarray*} \mathbb F \end{eqnarray*}$ bezeichnet man gern endliche Körper.

zur a) die Koeffizienten sollte man natürlich modulo 7 betrachten; Das erleichtert aber eigentlich nur die Rechnung, da keine so großen Zahlen auftreten.
Hier ist das aber kein Problem.
Modulo eines Polynoms ist genauso wie modulo Zahlen:
Du darfst X²+1 dazuzählen und abziehen wie du lustig bist.
Also:
-(x+1)(2+x) in $\begin{eqnarray*} \mathbb Z [X] \end{eqnarray*}$ berechnen.
- Gegebenenfalls mod 7 reduzieren.
- Ein mod X²+1 äquivalentes Polynom vom Grad kleiner-gleich 1 finden.

b) Das $\begin{eqnarray*} \mathbb F_7[X]/(X^2+1) \end{eqnarray*}$ ein Körper ist ist für die Aufgabenstellung nicht so wichtig (deswegen stand's ja auch in Klammern)
Schon was zu meinen restlichen Kommentaren überlegt?

22.07.2012, 17:07

Leon_20v

Auf diesen Beitrag antworten »

ne zu b) hab ich mir noch kaum gedanken gemacht, weil ich immer noch an der a) hänge.

Also bei der Rechnung ggf. modulo 7 heißt, wenn eine Zahl größer wie 6 ist, dann durch 7 teilen und den Rest schreiben? ja?

Ein mod X²+1 äquivalentes Polynom vom Grad kleiner-gleich 1 finden...

das beduetet ja ich muss entweder eine Zahl oder X^1 finden? Meinst du mit äquivalent, kongurent?

sorry das ich mich gerade so doof anstelle, ich lern heute schon 9h denn am Mittwoch ist Klausur unglücklich

unglücklich

22.07.2012, 17:14

leon_20v

Auf diesen Beitrag antworten »

also ich hab jetzt für die beiden gleichungen

x²+4x+2

raus

wenn ich das ganze jetzt modulo (x²+1) rechne, dann hab ich

3x+1 oder muss ich polynomdivision durchführen?

wie finde ich dann das äquivalente polynom? unglücklich

unglücklich

Anzeige

22.07.2012, 17:21

Captain Kirk

Auf diesen Beitrag antworten »

Nach 9h Stunden lernen am Stück könnte ich keinen geraden Gedanken fassen.
Pausen helfen.

Zitat:

-(x+1)(2+x) in $\begin{eqnarray*} \mathbb Z [X] \end{eqnarray*}$ berechnen.
- Gegebenenfalls mod 7 reduzieren.
- Ein mod X²+1 äquivalentes Polynom vom Grad kleiner-gleich 1 finden.

Das ist ein Kochrezept, wie man sowas auch allgemein machen kann. Und das gegebenfalls steht nicht umsonst da, hier ist der Fall nämklich nicht gegeben. Wobei dein vorgehen bei modulo prinzipiell richtig wäre.

Zitat:

das beduetet ja ich muss entweder eine Zahl oder X^1 finden?

Nein es gibt noch andere Polynome vom Grad 1 (das ^1 schreibt man nicht.), z.B. X+1,3x+5, 4X-2,...

Zitat:

Meinst du mit äquivalent, kongurent?

ja. (Die Kongruenz ist eine Äquivalenzrelation)

Zum 2. Post:

Zitat:

x²+4x+2

Tippfehler: x²+3x+2, das kongruente Polynom stimmt ja.

22.07.2012, 17:54

leon_20v

Auf diesen Beitrag antworten »

hmm da hast du mich falsch verstanden:

x²+3x+2 kommt raus wenn ich die beiden funktionen multipliziere,

dann muss dich doch

(x²+3x+2) / (x²+1) machen weil ich das ja im modulo habe oder?

dann erhalte ich ja als ergebnis: 1
und den Rest: 3x+1

oder? wie mach ich dann weiter?

22.07.2012, 18:10

leon_20v

Auf diesen Beitrag antworten »

b) hmm hier würde ich sagen x2-> R³ vll?
dann 7³?

// also darauf schließe ich weil ich hier eine andere aufgabe habe, da ist x³ in Z5 und da macht man 5^4 smile

smile

22.07.2012, 18:11

Captain Kirk

Auf diesen Beitrag antworten »

Und beim Modulorechnen geht's immer um den Rest, so wie du es ja selber schreibst:

Zitat:

Also bei der Rechnung ggf. modulo 7 heißt, wenn eine Zahl größer wie 6 ist, dann durch 7 teilen und den Rest schreiben?

Die Antowrt auf die a) ist also 3x+1.

22.07.2012, 18:38

leon_20v

Auf diesen Beitrag antworten »

b) hmm hier würde ich sagen x2-> R³ vll?
dann 7³?

// also darauf schließe ich weil ich hier eine andere aufgabe habe, da ist x³ in Z5 und da macht man 5^4 smile

22.07.2012, 18:58

Captain Kirk

Auf diesen Beitrag antworten »

Ich kann leider nicht nachvollziehen was du damit sagen willst.

Und von einer Aufgabe auf die nächste zu schließen ist keine so gute Idee.

22.07.2012, 19:01

leon_20v

Auf diesen Beitrag antworten »

hmm ok,

kannst du mir noch sagen wie ich auf den teil b) der aufgabe ansetzen muss? ich bin wirklich zu dumm glaub ich und in meinem skript steht natürlich auch nix gscheides unglücklich

unglücklich

22.07.2012, 22:02

Captain Kirk

Auf diesen Beitrag antworten »

(1,X) ist eine Basis.
Es gilt allgemein: ( $\begin{eqnarray*} 1,X,\ldots , X^{n-1} \end{eqnarray*}$ ) ist eine Basis von $\begin{eqnarray*} K[X]/(f(X)) \end{eqnarray*}$ falls deg(f)=n.

23.07.2012, 09:56

Mystic

Auf diesen Beitrag antworten »

Nur als ergänzende Bemerkung:

Falls $\begin{eqnarray*} x^2 \equiv -1 \mod p \end{eqnarray*}$ in $\begin{eqnarray*} \mathbb{Z}_p \end{eqnarray*}$ unlösbar ist, was genau für Primzahlen p der Form p=4k+3, insbesondere also auch p=7 der Fall ist, dann man den Übergang von den reellen zu den komplexen Zahlen "nachstellen", indem man einfach ein formales Element $\begin{eqnarray*} i=\sqrt{-1} \end{eqnarray*}$ zu $\begin{eqnarray*} \mathbb{Z}_p \end{eqnarray*}$ adjungiert, womit man dann einen Körper erhält, dessen Elemente also dann die Form

$\begin{eqnarray*} a+bi \quad (a,b \in \mathbb{Z}_p) \end{eqnarray*}$

haben... Gerechnet wird in diesem Körper ganz genau wie in den komplexen Zahlen, nur dass Real-und Imaginarteil immer mod p reduziert werden müssen...

23.07.2012, 10:21

leon_20v

Auf diesen Beitrag antworten »

danke für eure antworten, ich habs glaub smile

smile

bin gerade am kleinen fermat,

Ich soll

x^16 +1 mod 17 für alle x element Z17\{0}

berechnen.

Mein Ansatz hierzu ist:

x^17-1 +1 = 1 mod 17.

Wie mache ich hier dann weiter? Wenn x ne Zahl währe, wüsste ich es ungefähr, aber mit x weiß ich nicht wie ich das ausrechnen soll.

Danke smile

smile

23.07.2012, 13:09

Captain Kirk

Auf diesen Beitrag antworten »

Der kleine Fermat sagt doch:
$\begin{eqnarray*} x^{p-1] \equiv 1 \mod p \end{eqnarray*}$ für alle $\begin{eqnarray*} x \not \equiv 0 \mod p \end{eqnarray*}$
Hier ist p=17.

Damit kannst du $\begin{eqnarray*} x^{16} \end{eqnarray*}$ berechnen.

23.07.2012, 13:11

Captain Kirk

Auf diesen Beitrag antworten »

Zitat:

Original von Captain Kirk
Der kleine Fermat sagt doch:
$\begin{eqnarray*} x^{p-1} \equiv 1 \mod p \end{eqnarray*}$ für alle $\begin{eqnarray*} x \not \equiv 0 \mod p \end{eqnarray*}$
Hier ist p=17.

Damit kannst du $\begin{eqnarray*} x^{16} \end{eqnarray*}$ berechnen.

23.07.2012, 14:21

Leon_20v_unr

Auf diesen Beitrag antworten »

und wie geht des dann? da komm ich ja nicht weiter unglücklich

unglücklich

23.07.2012, 14:24

Captain Kirk

Auf diesen Beitrag antworten »

Um die Geadankenblockade zu lösen:
Berechne mal $\begin{eqnarray*} 1^{16} \end{eqnarray*}$ und $\begin{eqnarray*} 2^{16} \end{eqnarray*}$ modulo 17

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »