Teilerfremdheit mit Induktion?
Hallo :),
ich habe Folgendes im Buch
104 Number Theory Problems
von Titu Andreescu, Dorin Andrica, Zuming Feng
gesehen:
Und zwar habe ich eine Frage zu Unterpunkt 2, rot unterstrichen.
Warum ist das so?
Ich sehe das irgendwie nicht….
Danke sehr im Voraus und gute Nacht
2 Antworten
Langfassung :-) Sei d ein gemeinsamer Teiler von t_(k+1) und a.
Nach Konstruktion von t_(k+1) muss dann d auch in t_1 *…..* t_k * b aufgehen.
Nach Induktionsvoraussetzung geht aber d nicht in t_1 …. t_k auf.
Bleibt noch b, aber a und b sind als teilerfremd vorausgesetzt.
Also kann d nur gleich 1 sein.
Hallo :-), es ging hier eben um die Frage, was mit tk ist…
Ich hätte an Stelle des Autors eher gcd(a, tj) geschrieben. Würde das mehr Sinn machen?
Außerdem wird im Induktionsanfang der letzte Term auch ausgelassen
Kurzfassung: Wo soll denn ein gemeinsamer Teiler herkommen?
Beachte, dass stets gcd(n+a, a) = gcd(n, a) gilt.
D.h. es genügt, gcd(t1 * ... * tk * b, a) zu ermitteln.
Per Induktionsvoraussetzung hat keines der ti einen gemeinsamen Primfaktor mit a, und b hat es wegen gcd(a,b) = 1 auch nicht.
Ok, ich sehe das Problem. Ich würde allerdings davon ausgehen, dass der Autor meinte, dass gcd(a,ti) = 1 für i = k ebenfalls Teil der Induktionsvoraussetzung ist und er einfach nur übersehen hat, dass 1 ≤ i < j ≤ k hier den Fall i = k ausschließt.
Hallo, was ist mit tk?