Teilbarkeit

Neue Frage »

PamAnderson Auf diesen Beitrag antworten »
Teilbarkeit
Hallo,

ich habe hier eine Aufgabe aus einem alten Buch, das ich gestern bei einem Bekannten entdeckt habe und mich sofort rangemacht habe:

Zeigen Sie, dass x^2-x-2k für alle 0<k<m mit k Element natürliche Zahlen nur durch Zweierpotenzen := m teilbar ist.

Hätte jemand einen geeigneten Ansatz für diese Aufgabe? Thx und vG. Wink
tmo Auf diesen Beitrag antworten »

Irgendwie macht die Aussage für mich keinen Sinn verwirrt

Der genaue Wortlaut wäre von Vorteil.
PamAnderson Auf diesen Beitrag antworten »

ja, ich habe ein bisschen was vergessen:

Zeigen Sie, dass es nur dann ein x Element natürliche Zahlen für alle 0<=k<m gibt mit k,m € N, sodass x^2-x-2k durch m teilbar ist, wenn m eine Zweierpotenz ist.

Man hat also ein m. Nehmen wir an, dieses ist keine Zweierpotenz. Dann gibt es ein 0<=k<m, sodass es kein x für dieses k gibt, sodass x^2-x-2k durch m teilbar ist.
Nehmen wir an, dass m ist eine Zweierpotenz, so gibt es nach Aufgabenstellung zu jedem 0<=k<m ein x, sodass x^2-x-2k durch m teilbar ist.
HAL 9000 Auf diesen Beitrag antworten »

Da hatte gestern schon ein Kommilitone von dir den Anlauf

Zahlentheorie

genommen und ist schon bei der Formulierung glorreich gescheitert. Der Teil ist dir schon mal besser gelungen. Augenzwinkern


Zunächst mal ist nach Multiplikation mit 4 äquivalent zu




Für Zweierpotenzen ist also folgendes nachzuweisen: Für ist jeder Wert ein quadratischer Rest modulo .

Das geht relativ übersichtlich per Induktion über .
PamAnderson Auf diesen Beitrag antworten »

Hi Hal9000,

könntest du den Induktionsanfang kurz demonstrieren:

Sei d=3, also 2^d = 2^3 = 8, zz.: 8k+1 ist quadratischer Rest modulo 8 für alle 0<=k<8. ?

vG Wink
HAL 9000 Auf diesen Beitrag antworten »

Zitat:
Original von PamAnderson
Sei d=3, also 2^d = 2^3 = 8, zz.: 8k+1 ist quadratischer Rest modulo 8 für alle 0<=k<8. ?

Eigentlich reicht es ja für , aber ist im Prinzip egal.

Induktionsanfang sollte kein Problem sein, denn da ist nur zu betrachten - und dass 1 ein quadratischer Rest ist, nun... Augenzwinkern

Im Induktionsschritt zeigen wir basierend auf der Existenz eines mit , dass sowohl als auch mit quadratische Reste modulo sind. Denn wenn die Menge durchläuft, dann durchlaufen in ihrer Gesamtheit , was den Induktionsschritt komplettiert.
 
 
PamAnderson Auf diesen Beitrag antworten »

So das habe ich hinbekommen, ich meine aber noch gemäß der Aufgabenstellung, dass man noch zeigen sollte, dass für alle anderen m die Behauptung nicht gilt. Was könnte man da machen?

vG Wink
HAL 9000 Auf diesen Beitrag antworten »

Alle anderen Module besitzen mindestens einen ungeraden Primteiler, nennen wir ihn . Für die Erfüllbarkeit von



muss dann notwendig



lösbar sein. Klappt das für alle ? Augenzwinkern
PamAnderson Auf diesen Beitrag antworten »

Nein, aber warum? smile

Besten Dank bisher für Deine Hilfe Hammer
HAL 9000 Auf diesen Beitrag antworten »

Da und teilerfremd sind, durchläuft bereits für alle (!) Restklassen modulo , d.h., die Lösbarkeit von



für all diese ist gleichbedeutend mit der Forderung, dass sämtliche Restklassen modulo quadratische Reste sein müssten - tatsächlich trifft das aber nur auf die Restklassen



zu - und für ist nun mal . Augenzwinkern
PamAnderson Auf diesen Beitrag antworten »

Ok ich habe alles verstanden Freude , jetzt sollte die Aufgabe vollständig bearbeitet sein, oder?

vG Wink
HAL 9000 Auf diesen Beitrag antworten »

Wenn du diesen Teil

Zitat:
Original von HAL 9000
Im Induktionsschritt zeigen wir basierend auf der Existenz eines mit , dass sowohl als auch mit quadratische Reste modulo sind.

hier gepackt hast (was ja hier im Thread nicht näher beleuchtet wurde, wie das funktioniert), dann ist eigentlich alles komplett beisammen.
PamAnderson Auf diesen Beitrag antworten »

Könntest Du noch sagen, wie man das machen kann? Und eine Sache konnte ich mir dann noch nicht erklären: Warum sind nur die Restklassen bis [(p-1)/2]^2 modulo p quadratische Reste?

vG smile
HAL 9000 Auf diesen Beitrag antworten »

Zitat:
Original von PamAnderson
Warum sind nur die Restklassen bis [(p-1)/2]^2 modulo p quadratische Reste?

Die Werte sowie für umfassen alle möglichen Restklassen modulo , und die zugehörigen Quadrate sind dann für . Welche anderen quadratischen Reste soll es denn noch geben, wenn man bereits alle Restklassen quadriert hat??? Also wirklich, das hättest du dir auch selbst überlegen können. unglücklich


Und zu der Sache:

Zitat:
Original von HAL 9000
Im Induktionsschritt zeigen wir basierend auf der Existenz eines mit , dass sowohl als auch mit quadratische Reste modulo sind.

Da kommt man sicherlich schwieriger drauf - aber warum hast du da nicht schon oben eingehakt, statt deines "So, das habe ich hinbekommen." unglücklich

Na egal: Wir haben (als Induktionsvoraussetzung) die Existenz einer ganzen Zahl mit , es ist noch zu bemerken, dass da selbstverständlich ungerade sein muss, also . Gehen wir jetzt zum doppelt so großen Modul über, so folgt



mit entweder oder . Wir betrachten außerdem das Quadrat von , d.h.



Da nun ist, haben wir das gewünschte Ziel erreicht.

Anmerkung: Beim Faktor haben wir die Bedingung gebraucht, d.h., der Induktionsschritt funktioniert noch nicht für .
Neue Frage »
Antworten »



Verwandte Themen

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