ggT, Linearkombination

Neue Frage »

Gasti Auf diesen Beitrag antworten »
ggT, Linearkombination
Kann mir jemand nen Tip geben?

Beweisen sie, dass ggT(n-1, n²+n+1) immer 1 oder 3 ist.
Tip: finden sie eine mögliche Linearkombination


(Def der Lin-kombi: ra + sb = ggT(a,b) für r,s € Z )


ich hab durch einsetzen rausgefunden dass der ggT für alle n= 3k+1 immer 3 ist und für den Rest eben 1.

Wie beweise ich das?
der Tip sagt ja dass ich quasi diese Formel lösen müsste, oder?

r( n-1) + s (n²+n+1 ) = 1 oder 3

also 1. Fall für n= 3k+1 --> r(3k) + s ( 9k² + 9k + 3) = 3

das ist dann gekürzt: rk + s(3k² + 3k +1) = 1, richtig?

und jetzt weiß ich eigentlich ned weiter...ich muss doch zeigen, dass es r und s € Z gibt oder nicht?
wie?

Danke!
gasti Auf diesen Beitrag antworten »

gleich noch ne Frage...hab durch die Suchfunktion im Forum rausgefunden, dass man den ggT bei Polynomen durch Polynomdivision rausfinden kann....könnte mir das jemand mal genauer erklären?
Wenn ich bei meiner Aufgabe Polynomdivision mache, erhalte ich folgendes:

(n²+n+1) : (n-1) = n + 2 + 3 / (n-1) ...also einen Rest...kann ich hiermit irgendwas anfangen?
AD Auf diesen Beitrag antworten »

Indirekt schon: Es gilt ja für beliebige ganze Zahlen . Jetzt nimmst du für den Quotienten der Polynomdivision und erhältst:

gasti Auf diesen Beitrag antworten »

danke für die Antwort!

Ähm, und der Rest aus der Polynomdivision verschwindet dann?

Und was fange ich mit dem ergebnis ggt (n-1 , 3 ) an?

kannst du mir das näher erklären?
Ich muss doch beweisen dass der ggT immer 1 oder 3 ist .... bin schon ganz meschugge unglücklich

und kann man die linearkombination da nicht irgendwie mit einbauen?
gasti Auf diesen Beitrag antworten »

oh man sorry dass ich so doof bin

dass der ggt dann immer 1 oder 3 ist, ist bei dem ergebnis ja ersichtlich....

dankeschön!!!
AD Auf diesen Beitrag antworten »

Zitat:
Original von gasti
Ähm, und der Rest aus der Polynomdivision verschwindet dann?

Der verschwindet doch nicht, ist doch noch da! Oder was denkst du, wo die 3 herkommt?

Zitat:
Original von gasti
Und was fange ich mit dem ergebnis ggt (n-1 , 3 ) an?

Der größter gemeinsamer Teiler ist, wie der Name schon sagt, speziell auch ein Teiler der beteiligten Zahlen. Welche Teiler hat den die Zahl 3, es sind nicht allzu viele... Augenzwinkern
 
 
Neue Frage »
Antworten »



Verwandte Themen

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