Primzahlen und ggT

Neue Frage »

Jens84 Auf diesen Beitrag antworten »
Primzahlen und ggT
Hallo zusammen.
Ich habe eine Aufgabe gestellt bekommen, schaffe es aber nicht einen Anfang zu finden, wie diese Aufgabe zu lösen wäre.
Ich fange am besten mal mit meiner Aufgabe an:

Sei ganz und p eine Primzahl. Man ermittle in Abhängigkeit von n und p den größten gemeinsamen Teiler von und .

Nun denke ich, dass ich sogar schon das Ergebnis kenne. Durch einsetzen von verschiedenen Primzahlen und verschiedenen n habe ich immer wieder als ggT herausbekommen.
Mein Problem ist nicht unbedingt das berechnen, sondern viel mehr der Beweis.
Hat das vielleicht etwas mit dem euklidischen Algorithmus zu tun? Oder mit der eindeutigen Primfaktorzerlegung?
Ich habe mir auch schon überlegt, dass man auch als darstellen kann und dort ja auch der ggT irgendwie mit drinsteckt, aber vorangebracht hat mich das auch nicht.

Gibt es jemanden, der mir da behilflich sein kann? Ich bin über jede Hilfe dankbar, hoffe aber natürlich, dass ihr mir das möglichst simpel verständlich machen könnt.
Vielen Dank im Vorraus.

mfg
Jens
AD Auf diesen Beitrag antworten »

Zitat:
Original von Jens84
Durch einsetzen von verschiedenen Primzahlen und verschiedenen n habe ich immer wieder als ggT herausbekommen.

Dann hast du wohl nur n=2 und n=3 probiert, stimmt's? Für ist das nämlich falsch. Augenzwinkern


Ziehe doch einfach den euklidischen Algorithmus durch. Ich fange mal an:



letzteres geht natürlich schon nur noch für . Im folgenden müsstest du dann sehen, dass die Fälle "n gerade / n ungerade" zu unterscheiden sind.
Jens84 Auf diesen Beitrag antworten »

Das war schon mal eine große Hilfe. Vielen vielen Dank!
Ich habe dadurch auch prompt eine neue Vermutung aufstellen können, die schon viel besser aussieht und sich auch für Werte mit größeren n als richtig erweist! smile

Meine Rechnungen sehen wie folgt aus:

Für :

Für :

Für :

Für :



Also komme ich zu folgender Vermutung:
für n gerade.
für n ungerade.


So weit so gut. Zuerst einmal interessiert mich, ob ich damit richtig liege. (Dann wär ich für meine Verhältnisse schonmal stolz! Freude )
Aber wie für dich denn da jetzt am besten mal den Beweis? Kann ich da die Induktion verwenden? Und muss ich dann durch und ersetzen? Da bin ich mir noch ziemlich unsicher.

Wie ich im ersten Post schon gesagt habe bin ich für jede Hilfe dankbar.

Vielen Dank im Vorraus.
mfg
Jens
AD Auf diesen Beitrag antworten »

Zitat:
Original von Jens84
Also komme ich zu folgender Vermutung:
für n gerade.

Das sollte man natürlich noch zu vereinfachen. Augenzwinkern

Aber so ist es richtig, der andere Fall auch.

Zitat:
Original von Jens84
Kann ich da die Induktion verwenden?

Das ist zumindest formal die sauberste Variante.

Zitat:
Original von Jens84
Und muss ich dann durch und ersetzen?

"Müssen" ist immer ein starkers Wort - es ist aber eine naheliegende Option. Augenzwinkern
Jens84 Auf diesen Beitrag antworten »

Hallo nochmal und natürlich erneut: Vielen Dank für die Hilfe so weit.
Ich hab mich jetzt mal an der induktion versucht, bin jedoch ein wenig an meine Grenzen gestoßen.
Ich zeige einfach mal wie weit ich bin und was ich mir überlegt habe und hoffe, dass Hilfe möglich ist. traurig

Ich habe vor zwei Induktionen zu machen. Eine für gerade n und eine für ungerade n (da ich nicht weiß, wie ich beides in eine Induktion kriegen könnte).

Ich starte mal mit der Induktion für gerade n, wo ich dann auch stecken geblieben bin. Die Induktion für ungerade n müsste sich ja ähnen...

Also, gelernt habe ich das wie folgt:

Induktionsanfang:
Setze



Was zu zeigen war.

Induktionsvorraussetzung:
Es gelte für und :

Induktionsbehauptung:
Zu zeigen, dass für gilt:


Ich beginne jetzt, in dem ich für setze:


Ab hier war ich mir schon nicht mehr sicher. Dennoch hab ich versucht dass noch umzurechnen und hab folgendermaßen weitergemacht:


Hier ist vermutlich schon ein (oder DER) Fehler, dennoch wüsste ich auch anders nicht weiter. Weiterhin hab ich dann die folgenden Umformungen versucht:


Und ab hier wüsste ich (falls das tatsächlich richtig sein sollte) auch nicht mehr weiter.

Wo liegt mein Fehler oder wie kann ich weitermachen? Hab ich großen Mist gebaut?

Ich bin (wie immer) für jede Hilfe dankbar und hoffe mir kann geholfen werden.

mfg
Jens

P.S.: Ich habe die Schreibweise mit dem Ausrufezeichen beim Gleichheitszeichen einfach mal übernommen, weiß jedoch gar nicht richtig was das bedeutet, da ich das nicht kenne. Hat das explizit nur was mit dem euklidischen Algorithmus zu tun?
Jens84 Auf diesen Beitrag antworten »

Kann mir denn da niemand helfen? unglücklich

mfg
Jens
 
 
Neue Frage »
Antworten »



Verwandte Themen

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