3 teilt a^n + b^n - 1

[carlo berlingen]

a=1/2(7+sqrt(37)) , b=1/2(7-sqrt(37))
Leider habe ich keinen Anpack, wie ich dem Induktionsschluss bekommen kann. Die Gewieften unter euch haben bestimmt einen Tipp parat.
Dank und Gruß
Carlo

[Andreas Leitgeb]

carlo berlingen <carlo....@t-online.de> wrote:
> a=1/2(7+sqrt(37)) , b=1/2(7-sqrt(37))
> Leider habe ich keinen Anpack, wie ich dem Induktionsschluss bekommen
> kann. Die Gewieften unter euch haben bestimmt einen Tipp parat.

Nun, Beweis habe ich dafür nicht anzubieten, aber vielleicht eine
vage Idee, wie man zu einem Beweis kommen könnte...

Nach Muster-erkennung sehen die Terme für mich ein bisserl den
Termen ähnlich, mit denen die Fibonacci-Zahlen dargestellt
werden können... Wenn man das Vorgehen bei den Fibonacci-
Zahlen von Rekursion zur Formel rückwärts geht und eben die
anderen Zahlen einbaut, kommt man vielleicht auf eine Rekursions-
formel ähnlich zu der der Fibonacci Zahlen und diese Formel (und
die Startwerte dazu) könnten dann die Teilbarkeit durch 3 offen-
sichtlich machen...

[Alfred Flaßhaar]

Versuche zuerst herauszubekommen, für welche n die Behauptung wahr sein
könnte - probieren.

Gruß, Alfred

[JVR]

a + b == 1 (mod 3)
ab == 0 (mod 3)
Angenommen es sei a^m + b^m == 1(mod 3) für alle m <= n, dann ist
(a^n + b^n)(a+b) == a^(n+1) + b^(n+1) + ba^n + ab^n == 1(mod 3)
a^(n+1) + b^(n+1) + ab(a^(n-1)) + ab(b^(n-1)) == 1 (mod 3)

[Ralf Goertz]

Am Sun, 23 Apr 2023 09:48:59 -0700 (PDT)
schrieb JVR <jrenne...@googlemail.com>:

Ja, das schöne an dieser Lösung ist, dass man sich gar nicht um a und b
kümmern muss (außer zu sehen, dass ab=3 ist, aber da a und b konjugiert
sind und ihr Produkt daher rational ist, ist die Idee schnell da). In
der Tat funktioniert das ja auch mit beliebigen a=0 (mod 3) und b=1 (mod
3) (oder umgekehrt), weil jede Potenz von a und b nichts an dieser
Eigenschaft ändert.

[Alfred Flaßhaar]

Da ich recht gut schlecht sehen kann, habe ich das 1/2 versehentlich
nicht in die Klammerpotenz mit einbezogen. Das wird dann aber interessant.

[Martin Vaeth]

carlo berlingen <carlo....@t-online.de> schrieb:
> a=1/2(7+sqrt(37)) , b=1/2(7-sqrt(37))

ab = 3,
a + b = 7.

Also sind nach Vieta a, b die Nullstellen von x^2 - 7x + 3.
Dies ist das charakteristische Polynom der linearen
Rekursionsgleichung

x_{n+1} = 7x_n - 3x_{n-1} (*)

die deswegen die allgemeine Lösung ca^n + db^n hat.
Wir haben damit also die Rekursionsformel
a^n + b^n = x_n
wenn wir c = d = 1 wählen, also die Anfangswerte
x_0 = a^0 + b^0 = 2
x_1 = a^1 + b^1 = a + b = 7
in der Rekurionsformel (*) benutzen.

Nebenbei sehen wir hier, dass für n = 0, 1 die Zahlen
x_0 - 1 = 1 und x_1 - 1 = 6 durch 3 teilbar sind.

Nun kommt man mit der Rekursionsformel zur Lösung:
Lassen x_n und x_{n-1} modulo 3 den Rest 1, so rechnen
wir modulo 3, dass das auch für x_{n+1} gilt:

x_{n+1} = 7x_n - 3x_{n-1} = 7 - 3 = 4 = 1

[Martin Vaeth]

Martin Vaeth <mar...@mvath.de> wrote:
> carlo berlingen <carlo....@t-online.de> schrieb:
>> a=1/2(7+sqrt(37)) , b=1/2(7-sqrt(37))
>
> ab = 3,
> a + b = 7.
>
> Also sind nach Vieta a, b die Nullstellen von x^2 - 7x + 3.
> Dies ist das charakteristische Polynom der linearen
> Rekursionsgleichung
>
> x_{n+1} = 7x_n - 3x_{n-1} (*)
>
> die deswegen die allgemeine Lösung ca^n + db^n hat.
> Wir haben damit also die Rekursionsformel
> a^n + b^n = x_n
> wenn wir c = d = 1 wählen, also die Anfangswerte
> x_0 = a^0 + b^0 = 2
> x_1 = a^1 + b^1 = a + b = 7
> in der Rekurionsformel (*) benutzen.
>
> Nebenbei sehen wir hier, dass für n = 0, 1 die Zahlen
> x_0 - 1 = 1 und x_1 - 1 = 6 durch 3 teilbar sind.

Bah: 1 ist ja nicht durch 3 teilbar: Für n = 0 ist die
Behauptung tatsächlich falsch. Wir müssen es für die
Rekursion also noch für n = 2 verifizieren:

x_2 = 7x_1 - 3x_0 = 49 - 6 = 43

x_2 - 1 = 42 ist nun tatsächlich durch 3 teilbar, so
dass der weitere Schluss dann für n = 3, 4, ...
gerettet ist:

[Alfred Flaßhaar]

Am 23.04.2023 um 18:23 schrieb Andreas Leitgeb:
> carlo berlingen <carlo....@t-online.de> wrote:
>> a=1/2(7+sqrt(37)) , b=1/2(7-sqrt(37))

(...)

> Wenn man das Vorgehen bei den Fibonacci-
> Zahlen von Rekursion zur Formel rückwärts geht und eben die
> anderen Zahlen einbaut, kommt man vielleicht auf eine Rekursions-

> formel ähnlich zu der der Fibonacci Zahlen...

(...)

Man kommt tatsächlich darauf. Es erinnert an eine uralte Übungsaufgabe,
für die es den Wochenendextrapunkt auf dem Übungsschein gab. Besonders
interessant sind die Primteiler der Folgenglieder.

Gruß, Alfred Flaßhaar

[Alfred Flaßhaar]

Am 24.04.2023 um 09:59 schrieb Alfred Flaßhaar:
> Am 23.04.2023 um 18:23 schrieb Andreas Leitgeb:
>> carlo berlingen <carlo....@t-online.de> wrote:
>>> a=1/2(7+sqrt(37)) , b=1/2(7-sqrt(37))
>
> (...)
>

p. s.

u_(n+2) = 7*u_(n+1) - 3*u_n + 3

[Andreas Leitgeb]

Für den Schritt war ich dann zu faul... Also Danke für die
Ergänzung :-)

Für die Aufgabe kommt es aber ja gar nicht auf die Primteiler
der Folgenglieder an - außer halt notwendigerweise, dass 3 nicht
dabei ist ;-)

[Alfred Flaßhaar]

Ja, ist schon klar, aber es macht Freude, damit zu spielen. Und es ist
bemerkenswert, daß fast immer nur kleine und sehr große Primteiler darin
stecken.

[Andreas Leitgeb]

Alfred Flaßhaar <Alfred.F...@gmx.de> wrote:
> Am 24.04.2023 um 19:32 schrieb Andreas Leitgeb:
>> Alfred Flaßhaar <Alfred.F...@gmx.de> wrote:
>>> Am 24.04.2023 um 09:59 schrieb Alfred Flaßhaar:
>>>> Am 23.04.2023 um 18:23 schrieb Andreas Leitgeb:
>>>>> carlo berlingen <carlo....@t-online.de> wrote:
>>>>>> a=1/2(7+sqrt(37)) , b=1/2(7-sqrt(37))
>>>> (...)
>>> p. s.
>>> u_(n+2) = 7*u_(n+1) - 3*u_n + 3

>> (...)

>> Für die Aufgabe kommt es aber ja gar nicht auf die Primteiler
>> der Folgenglieder an - außer halt notwendigerweise, dass 3 nicht
>> dabei ist ;-)
> Ja, ist schon klar, aber es macht Freude, damit zu spielen. Und es ist
> bemerkenswert, daß fast immer nur kleine und sehr große Primteiler darin
> stecken.

Ich wäre schon ziemlich überrascht, wenn das nicht nur eine zufällige
Beobachtung unter "niederen"(also jedenfalls unter 1 googol) Indizes
wäre...

Andernfalls hätten wir wohl einen schönen Generator für beliebig große
Primzahlen - nachdem man die kleinen mal aus den Folgengliedern raus-
dividiert hat... ;-)