Zahlentheorie

Neue Frage »

frustriert Auf diesen Beitrag antworten »
Zahlentheorie
Guten Morgen!

Ich habe beim Bearbeiten der folgenden Aufgabe ein Problem:

Sei p eine Primzahl, n aus N, (p,n)=1. Seien x, a aus Z, (p,a)=1 und aus N.
Ist , dann existiert ein mod p eindeutig bestimmtes aus Z mit .

Als Hinweis war gegeben, dass man mit der binomischen Entwicklung von arbeiten soll. Das habe ich durch auch gemacht. Jetzt weiß ich aber nicht mehr weiter. Kann mir bitte jemand helfen?
Abakus Auf diesen Beitrag antworten »
RE: Zahlentheorie
Zitat:
Original von frustriert
Als Hinweis war gegeben, dass man mit der binomischen Entwicklung von arbeiten soll. Das habe ich durch auch gemacht. Jetzt weiß ich aber nicht mehr weiter. Kann mir bitte jemand helfen?


Bisher hast du die binomische Summe also. Nun könntest du versuchen, diese weiter auszurechnen:



Das ist erstmal eine Idee. Führt das zu was ?

Grüße Abakus smile
AD Auf diesen Beitrag antworten »

Für und gilt



Das reduziert die binomische Summe gewaltig, auf nur noch zwei Summanden, nämlich die für k=0 und k=1. Augenzwinkern
frustriert Auf diesen Beitrag antworten »

Danke erstmal!

Mit dem letzten Tip vereinfacht sich also meine Kongruenz also zu .

Wie geht es jetzt aber weiter? ich verstehe es einfach nicht...
AD Auf diesen Beitrag antworten »

Wegen gibt es ein mit . Durch Einsetzen in die soeben von dir verkürzte binomische Summe folgt

.

So, und über das dürfen wir noch frei verfügen! Keine Ahnung, wie man jetzt weiter vorgehen könnte? Denk dran, es soll am Ende rauskommen, durch passende Wahl von ...
frustriert Auf diesen Beitrag antworten »

Wahrscheinlich muss man so wählen, dass der letzte Teil der Kongruenz equivalent zu 0 mod ist.
Aber was hast du für eingesetzt?
 
 
AD Auf diesen Beitrag antworten »

Äh ja, da ist mir ein Faktor durch die Lappen gerutscht - ich meine natürlich

,

sorry.
frustriert Auf diesen Beitrag antworten »

Ich habe leider trotzdem keine Ahnung, wie ich auf die richtige Wahl von komme...

Und zu dem vorherigen Schritt: Darf ich überhaupt a für x^n einsetzen, obwohl die jetzige Kongruenz nicht sondern ist?
AD Auf diesen Beitrag antworten »

Dein Ziel ist doch der Nachweis, dass es genau ein gibt mit

.

Wegen (*) ist das äquivalent zu

,

was wiederum nach Division durch äquivalent zu



ist. Immer noch keine Idee, was jetzt die Lösbarkeit von (**) bzgl. betrifft? Augenzwinkern
frustriert Auf diesen Beitrag antworten »

Vielleicht ? Aber dann wäre ja nicht unbedingt aus Z.

Tut mir leid, besser bekomme ich es echt nicht hin unglücklich
AD Auf diesen Beitrag antworten »

Mit Substitution ist doch nur die Gleichung zu lösen! Und aus den Voraussetzungen kannst du ziemlich schnelle folgern. Über die Lösbarkeit einer so einfachen linearen Kongruenz musst du doch irgendwas wissen!
frustriert Auf diesen Beitrag antworten »

Also noch ein Versuch:

Da sowohl n als auch x laut Voraussetzung teilerfremd mod p sind, sind sie invertierbar. Demnach müsste die Lösung also lauten.

Ist das jetzt richtig?

Danke schonmal für die viele Mühe mit mir!
AD Auf diesen Beitrag antworten »

Ja, ist richtig, wobei es auf die genaue Darstellung der Lösung gar nicht drauf ankommt. Wichtig ist nur, dass sie existiert und modulo p eindeutig ist.

Eine Kleinigkeit aber noch:
Zitat:
Original von frustriert
als auch x laut Voraussetzung teilerfremd mod p sind

Das ist nicht direkt vorausgesetzt, folgt aber durch kurze Argumentation aus (p,a)=1 .
frustriert Auf diesen Beitrag antworten »

Alles klar!

Vielen Dank nochmal!!!
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »