Aufgabe für knobelnde Diophanten

[Alfred Flaßhaar]

Zu lösen ist ohne Hilfe einer numerischen Keule in positiven ganzen
Zahlen die Gleichung 2*x^2 - 17*y^2 = 1. Volle Punktzahl gibt es für die
allgemeine Lösung (x_n; y_n) mit x_n = f(n) und y_n = g(n), wobei f(n)
und g(n) Terme sind, und der Index n = 1, 2, .... durchläuft.

Mit dieser Aufgabe möchte ich an Prof. Aleandru Lupas erinnern, der im
August 2007 verstarb.

Freundliche Grüße, Alfred Flaßhaar

[neu...@tuhh.de]

Moin Alfred,
nach dem letzten Ausflug liegt das herangehen nahe:

Man findet z.B. (versprochen ohne numerische Keule):
2*3² -17*1²= 1,
2*207² - 17*71²= 1
...

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
..
.
.
.
.
.
.
.

Für sqrt(2/17)=y/x wäre 2x²= 17y² oder 2x² -17y²~ 1
Da die Wurzel eine Irrationale Zahl ist, wäre eine "gute" rationale Näherung eventuell sqrt(2/17)= y/x eine mögliche Lösung.
Kettenbrüche liefern im gewissen Sinn beste rationale Lösungen (kleine Nenner) und man kann hoffen (oder weiß man?),
daß auch mal 1 als (kleinstmögliche) Differenz auftritt.
Das ist für (3,1), (207,71) der Fall, aber wie geht es weiter?
Mir scheint, daß die Reste periodisch (o.ä.) mit dem Grad der Kettenbruchentwicklung auftreten,
bin aber nicht so gut drauf, daß ich mich daran machen mag! :-(
Wäre aber an einer Lösung interessiert!

VG Siggi N.

[Wolfgang Rave]

Alfred Flaßhaar schrieb am Donnerstag, 15. September 2022 um 16:15:43 UTC+2:

> Zu lösen ist ohne Hilfe einer numerischen Keule in positiven ganzen
> Zahlen die Gleichung 2*x^2 - 17*y^2 = 1. Volle Punktzahl gibt es für die
> allgemeine Lösung (x_n; y_n) mit x_n = f(n) und y_n = g(n), wobei f(n)
> und g(n) Terme sind, und der Index n = 1, 2, .... durchläuft.
>

> Freundliche Grüße, Alfred Flaßhaar

hi Alfred,

der Kettenbruch von 8,5 = 17/2 ergibt sich zu [2,1;1,4,1,10] mit Periode 4.
Damit erhält man (3;1), (207,71), (14487, 4969), ... als Lösungen.
Die "Zwischenterme" (35,12), (2449,840), ... liegen "knapp daneben" (= 2).
Das Bildungsgesetz für die x_n, y_n ist jetzt nicht mehr schwer ... (und wird
dem geneigten Leser als Übungssaufgabe überlassen).

herzlich, Wolfgang.

Spoiler








x_n: mal 70 -3
y_n: mal 70 -1

[Klaus-R. Loeffler]

Ja aber: Mit x_0 = 3, y_0 = 1 ist doch y_1 = 71 <> y_0 -1.
Und wäre die angegebene Rekursionsgleichung – die für den Schritt von n=1 zu n = 2 ja die richtigen Werte für y_2 und x_2 liefert, - allgemein für n > 0 richtig, müsste die sich durch Einsetzen deiner Rekursion ergebende Gleichung 6x_n - 17y_n = 35 gelten, und das ist nur für n = 1 der Fall.
Bleibt mir - trotz geneigtem Übungs-Saufen - unklar.
Herzlicher Gruß , Klaus-R.

[Wolfgang Rave]

mathe...@googlemail.com schrieb am Samstag, 17. September 2022 um 16:58:48 UTC+2:

> Ja aber: Mit x_0 = 3, y_0 = 1 ist doch y_1 = 71 <> y_0 -1.
> Und wäre die angegebene Rekursionsgleichung – die für den Schritt von n=1 zu n = 2 ja die richtigen Werte für y_2 und x_2 liefert, - allgemein für n > 0 richtig, müsste die sich durch Einsetzen deiner Rekursion ergebende Gleichung 6x_n - 17y_n = 35 gelten, und das ist nur für n = 1 der Fall.
> Bleibt mir - trotz geneigtem Übungs-Saufen - unklar.
> Herzlicher Gruß , Klaus-R.

hi all,
Oh sorry, ich seh grad, ich hab gepfuscht. Für n>1 gilt:
also x_n = 70*x_n-1 - x_n-2 (Rekursion 2. Ordnung)
und y_n = 70*y_n-1 - y_n-2 (dito).
Komisch: x_1 = 70*x_0 - 3 (=69*x_0)
und y_1 = 70*y_0 +1 (=71*y_0).
Bis auf den ersten stimmt die Rekursion, aber n=1 is schräg.
Ich nehme derweil außerdem an, daß Kettenbruch als "numerische Keule" gilt
und deshalb für diese Aufgabe evtl. nicht erlaubt ist (?).
Ich bitte um Vergebung ...

verpeilte Grüsze, euer Wolfgang.

[neu...@tuhh.de]

Wie ich mir dachte:

Der Kettenbruch liefert außerdem (periodisch) auch Lösungen für 2x² -17y²= -9 (z.B. für 2*2² -17*1²= -9)
und 2x² -17y²= 2 (z.B. für 2*1 -17*0²= 2 und 2*35² -17*12²= 2*1225 -17*144= 2450 -2448= 2 ...)

Heißt das aber auch, daß es außer für 2x² -17y²= k (k=1,2,-9) keine Lösungen für irgendein Anders k gibt!?
2*1² -17*1²= -15 also nein!
Gibt es dann auch Lösungen von 2x² -17y²= 1 außer die aus der Kettenbruch-Lösung?

VG Siggi N.

[Wolfgang Rave]

neu...@tuhh.de schrieb am Samstag, 17. September 2022 um 19:42:06 UTC+2:

> Wie ich mir dachte:
>
> Der Kettenbruch liefert außerdem (periodisch) auch Lösungen für 2x² -17y²= -9 (z.B. für 2*2² -17*1²= -9)
> und 2x² -17y²= 2 (z.B. für 2*1 -17*0²= 2 und 2*35² -17*12²= 2*1225 -17*144= 2450 -2448= 2 ...)
>
> Heißt das aber auch, daß es außer für 2x² -17y²= k (k=1,2,-9) keine Lösungen für irgendein Anders k gibt!?
> 2*1² -17*1²= -15 also nein!
> Gibt es dann auch Lösungen von 2x² -17y²= 1 außer die aus der Kettenbruch-Lösung?
>
> VG Siggi N.

hi all,
nein, die gibt es nicht. Der euklidische Algorithmus (Kettenbruch)
liefert die besten Approximationen mit den kleinsten Termen.
In diesem Spezialfall einer "halbzahligen" Pell-Gleichung gibts
nur eine Ausnahme: (6,2), (414,142), ... ergibt eine 4 < 9. Alle
anderen Normen (=Werte der Gleichung) sind größer als die 9.

Hat hier noch wer was zu bieten ohne "numerische Keule" bzw.
eine Erklärung für die schrägen Werte bei n=1 (Rekursion paßt nicht!)?

lG, Wolfgang.

PS: Siggi, guck doch mal, ob Du auch das Bildungsgesetz für die 4 findest.
Wie heißt das nächste Lösungspaar? ;-)

[neu...@tuhh.de]

Moin Wolfgang, moin alle.


Ja, aber das ist doch offensichtlich
2x² - 17y²= 4 <--> 2(2x)² -17(2y)²= 1 und damit die "bekannten" Lösungen.
Und damit auch 2x² - 17y²= 9 und 2*9² -17*3²= 9(18-17)= 9 u,s,w, ... u.s.w.

Aber nur weil der euklidische Algorithmus nicht mehr liefert ...,
2x² - 17y²= 1, 2x² - 17y²= 2 und 2x² - 17y²= -9
reicht das denn für ein konsequentes Nein.
Siehe eben auch zuvor schon:

Wer weiß mehr?

VG Siggi N.

[Alfred Flaßhaar]

Am 15.09.2022 um 16:15 schrieb Alfred Flaßhaar:
> Zu lösen ist ohne Hilfe einer numerischen Keule in positiven ganzen
> Zahlen die Gleichung 2*x^2 - 17*y^2 = 1. Volle Punktzahl gibt es für die
> allgemeine Lösung (x_n; y_n) mit x_n = f(n) und y_n = g(n), wobei f(n)
> und g(n) Terme sind, und der Index n = 1, 2, .... durchläuft.
>

p. s.

_Zur Klarstellung:_ Bei Aufgaben dieser Art ist hauptsächlich der
Lösungsweg die Lösung. Deshalb sollte als "numerische Keule"
ausgeschlossen sein, daß der Lösungsweg nur aus Dateneingabe, "Enter"
und Ergebnisausgabe nach geheimnisvoller Berechnung einer Software
besteht. Software dieser Art gibt es reichlich. Dagegen ist es
sicherlich sinnvoll, Berechnungen, die im Prinzip "zu Fuß" machbar sind,
von einem CAS schneller ausführen zu lassen. Letzteres trifft wohl
offensichtlich auch auf die Kettenbruchentwicklung zu, die daher aus
meiner Sicht keine numerische Keule ist. Und sind die gesuchten Terme
für f(n) und g(n) mit Hilfe der Kettenbruchmethode erzeugbar?

Interessant istfür mich, daß die Kettenbruchmethode auch auf den
Gleichungstyp a*x^2 - b*y^2 = 1 (a > 1) angewendet wurde. In älterer
Literatur habe ich dazu noch nichts gefunden.

Freundliche Sonntagsgrüße, Alfred Flaßhaar

[Wolfgang Rave]

Alfred Flaßhaar schrieb am Sonntag, 18. September 2022 um 11:05:37 UTC+2:
> Am 15.09.2022 um 16:15 schrieb Alfred Flaßhaar:
> > Zu lösen ist ohne Hilfe einer numerischen Keule in positiven ganzen
> > Zahlen die Gleichung 2*x^2 - 17*y^2 = 1. Volle Punktzahl gibt es für die
> > allgemeine Lösung (x_n; y_n) mit x_n = f(n) und y_n = g(n), wobei f(n)
> > und g(n) Terme sind, und der Index n = 1, 2, .... durchläuft.
> >
>

> Freundliche Sonntagsgrüße, Alfred Flaßhaar

hi all,
also zurück zur Ausgangsfrage: Gesucht x_n = f(n), y_n = g(n).
2x^2 - 17y^2 = 1 |*2
4x^2 - 34y^2 = 2 |X = 2x
X^2 - 34y² = 2

Wir landen also bei Pell X^2 - 34y^2 = 2 (mit D=34 und = 2), nicht überraschend.
Deren Lösungen sind bestens bekannt (siehe "Pellsche Gleichung" und/oder
diophantische Approximationen bei wiki oder sonstwo): (6,1), (414,71), (28974,4969),...
Für = 1: (35,6), (2449,420), (171.395,29.394), ...
Und deren f(n) nebst g(n) sind ebenfalls bestens bekannt.

Für unsere gesucht Lösung müssen wir also bloß deren X-Werte durch 2 teilen,
entsprechend ergeben sich die f(n) und g(n) analog. Das fussel ich jetzt hier
nicht mehr im Detail zusammen ("für den geneigten Leser", ahemm).

herzlich, Wolfgang.

[neu...@tuhh.de]

Wolfgang, hatte ich Dich falsch verstanden? Pardon!
Aber es gibt wohl diverse Rangehens-Weisen.

VG SiggiN.

[Wolfgang Rave]

neu...@tuhh.de schrieb am Montag, 19. September 2022 um 10:19:05 UTC+2:

> Wolfgang, hatte ich Dich falsch verstanden? Pardon!
> Aber es gibt wohl diverse Rangehens-Weisen.
>
> VG SiggiN.

hi all und Siggi,
keine Panik, alles gut. -
Ich hab derweil mit Pells vom Typ 2x^2 - Dy^2 = 1 bissi rumgespielt.
Die haben generell nur Lösungen, wenn D = 2n*k^2 - 1. Wie zB 17 = 2*3^2-1.
Also 1 < D € |N = 7, 17, 23, 31, 47, 49, 71, 79, 97, ...
Ansonsten liefert die Glchg sehr oft den Wert 2 (nicht überraschend), und den
Zusammenhang mit dem "normalen" Pell hatten wir ja schon gezeigt.

Hübsches Spielchen, euer Wolfgang.

[neu...@tuhh.de]

Moin alle.

Ich habe auch nochmal ein bißchen mit der Gleichung 2x² -17y²= 1 gespielt .
Wie man mit der Kettenbruchmethode Lösungen findet ist wohl ausreichend diskutiert,
aber meine Frage ist immernoch, sind das denn dann die einzigen (*)!?

Ich habe mal ein Programm geschrieben, das alle rationalen Zahlen x/y aufzählt
- Stern-Brocot-Folge (A002487 in OEIS[1]).
In die originäre Gleichung eingesetzt testet man für alle denkbaren Kombinationen (x,y) ob sie Lösungen sind.
Es finden sich (in einem Überschaubaren Zahlenraum(**)) aber keine weiteren Lösungen!?
("Richtig" durchlaufen - ... , 1/2, 2/1, 1/3, 3/3, 2/3, 3/1, ...ergeben sich Zahlengruppen mit 2^k , k=1,2,,3,... Gliedern,
so daß sich recht schnell längere Laufzeiten ergeben.)

Für 2x² -y²= 1 findet man (**) dabei auch nur die Lösungen der Kettenbruchmethode!

Alfred, weißt Du einen Beweis für (*)

[Alfred Flaßhaar]

Am 21.09.2022 um 14:25 schrieb neu...@tuhh.de:
> Wolfgang Rave schrieb am Mittwoch, 21. September 2022 um 10:31:06 UTC+2:
>> neu...@tuhh.de schrieb am Montag, 19. September 2022 um 10:19:05 UTC+2:
>>

(...)
>> (...), und den

>> Zusammenhang mit dem "normalen" Pell hatten wir ja schon gezeigt.

Die Stelle finde ich nicht?

(...)

> Wie man mit der Kettenbruchmethode Lösungen findet ist wohl ausreichend diskutiert,

Bin anderer Meinung. Quellen-/Literaturangaben wären wünschenswert.

> aber meine Frage ist immernoch, sind das denn dann die einzigen (*)!?

Für die klassische Gleichung x^2 - D*y^2 = 1 (D nicht quadratisch)
liefert die Kettenbruchmethode alle Lösungen. Zur allgemeineren
Gleichung a*x^2 - b*y^2 = c gibt es etliche auch neuere Literatur, die
so richtig in die Algebra driftet. Das geht schnell in die Ringtheorie,
die nach meiner Meinung nicht hier nach drd gehört. Die ursprünglich aus
gewissen Gründen im Gedenken an Prof. Lupas gestellte Aufgabe sollte
hier mit Hilfe einfacherer Verfahren aus der Literaur gelöst werden. Mir
jedenfalls tat es gut, Vergessenes aufzufrischen und Bücher abzustauben.
Und eine friedliche Diskussion ist auch etwas Feines.

Die Gleichung 2*x^2 - ^7*y^2 = 1 habe ich völlig anders ohne
Kettenbruchentwicklung gelöst. Der Lösungsweg ist in "Gelfond, Die
Auflösung von Gleichungen in ganzen Zahlen" wunderbar schülergerecht
beschrieben und hat mmich an die Jugendzeit erinnert. Ähnlich steht es
auch im Bundschuh. Und richtig detailliert findet man den Lösungsweg in
"Andreescu/Andrica, An Introduction to Diophantine Equations". Also habe
ich die sog. Pellsche Resolvente zur Aufgabe gelöst und daraus die
Lösung der Aufgabe entwickelt. Damit werden _alle_ Lösungen dargestellt.
>
(...)

>
> Für 2x² -y²= 1 findet man (**) dabei auch nur die Lösungen der Kettenbruchmethode!
>

Das ist eine sog. negative Pellsche Gleichung. Und die ist mit Vorsicht
zu genießen. Bundschuh gibt auf S. 192 dazu Auskunft.

Es tut mir leid, wenn ich mich hier etwas kantig ausgedrückt habe. Aber
wie ich schon früher schrieb, ist die Lösung solcher Aufgaben
hauptsächlich der begründete Lösungsweg. Dabei müssen hier in drd nicht
die Klassiker von Perron, Olds, Khintchine, ... mitwirken. Dann hätte
ich die Aufgabe in "böser" Absicht (Ringtheorie, komplexe Lösung) in dsm
gestellt.

Bei Interesse sende ich gern meine Lösung als html. Das ist nicht für
professionelle Zwecke hart strukturiert, sondern als Lockmittel zur
Förderung der natürlichen Neugier jüngerer Nichtprofis gedacht.

Viele Grüße, Alfred Flaßhaar

[Wolfgang Rave]

Alfred Flaßhaar schrieb am Mittwoch, 21. September 2022 um 15:38:18 UTC+2:
> Am 21.09.2022 um 14:25 schrieb neu...@tuhh.de:
> > Wolfgang Rave schrieb am Mittwoch, 21. September 2022 um 10:31:06 UTC+2:
> >> neu...@tuhh.de schrieb am Montag, 19. September 2022 um 10:19:05 UTC+2:
> >>
> (...)
> >> (...), und den
> >> Zusammenhang mit dem "normalen" Pell hatten wir ja schon gezeigt.
> Die Stelle finde ich nicht?
>

2x^2 - Dy^2 = 1 | *2
4x^2 - 2Dy^2 = 2 | X = 2x
X^2 - 2Dy^2 = 2
Voilá. Mit a € |N statt 2 gilts allgemein.

Merci für die Literaturtipps.

herzlich, Wolfgang.

[Wolfgang Rave]

Alfred Flaßhaar schrieb am Mittwoch, 21. September 2022 um 15:38:18 UTC+2:

> Die Gleichung 2*x^2 - ^7*y^2 = 1 habe ich völlig anders ohne
> Kettenbruchentwicklung gelöst. Der Lösungsweg ist in "Gelfond, Die
> Auflösung von Gleichungen in ganzen Zahlen" wunderbar schülergerecht
> beschrieben und hat mmich an die Jugendzeit erinnert. Ähnlich steht es
> auch im Bundschuh. Und richtig detailliert findet man den Lösungsweg in
> "Andreescu/Andrica, An Introduction to Diophantine Equations". Also habe
> ich die sog. Pellsche Resolvente zur Aufgabe gelöst und daraus die
> Lösung der Aufgabe entwickelt. Damit werden _alle_ Lösungen dargestellt.

2x^2 - 7y^2 = 1 ist (mit Kettenbruch) ja sehr einfach.
(2,1) sieht man sofort, (58,31), (1738, 929), (52082,27839), ...
die "Zwischenlösungen" (15,8), (449,240), (13455, 7192), ...
(mit Norm = 2) sind gerade die Lösungen für den Pell mit D=14,
wenn man den geraden Wert noch durch 2 teilt, fertig. Siehe oben.
Und fürs "große Bildungsgesetz" bin ich, wie oben, irwie zu faul (sorry!).
Wenn noch wer Lust hat, das auszufummeln ...
Pellsche Resolvente sagt mir gar nix. Bin aber auch nur Zth-Amateur ...!
Erst mal Gelfond und Andreescu beatellen, dann sehn wir weiter.

euer Wolfgang.

[Wolfgang Rave]

Alfred Flaßhaar schrieb am Mittwoch, 21. September 2022 um 15:38:18 UTC+2:

> > Für 2x² -y²= 1 findet man (**) dabei auch nur die Lösungen der Kettenbruchmethode!
> >
> Das ist eine sog. negative Pellsche Gleichung. Und die ist mit Vorsicht
> zu genießen. Bundschuh gibt auf S. 192 dazu Auskunft.
>

Ups - wieso Vorsicht? 2x^2 - y^2 = 1 <=> y^2 - 2x^2 = -1.
daher "negativ", hat aber für unendlich viele D's haufenweise Lösungen.
Grobe Schätzung: Etwa 1/4 aller 1 < D < 10.000 liefern Lösungen.

>
> Es tut mir leid, wenn ich mich hier etwas kantig ausgedrückt habe. Aber
> wie ich schon früher schrieb, ist die Lösung solcher Aufgaben
> hauptsächlich der begründete Lösungsweg. Dabei müssen hier in drd nicht
> die Klassiker von Perron, Olds, Khintchine, ... mitwirken. Dann hätte
> ich die Aufgabe in "böser" Absicht (Ringtheorie, komplexe Lösung) in dsm
> gestellt.
>

Keine Sorge, Alfred, niemand nimmt Dir hier was krumm.

>
> Bei Interesse sende ich gern meine Lösung als html. Das ist nicht für
> professionelle Zwecke hart strukturiert, sondern als Lockmittel zur
> Förderung der natürlichen Neugier jüngerer Nichtprofis gedacht.
>

Gerne - wenn: Dürfen auch, ahemm, ältere Nichtprofis mitspielen? ;-)
>
> Viele Grüße, Alfred Flaßhaar

Wolfgang.

[Alfred Flaßhaar]

Am 21.09.2022 um 18:31 schrieb Wolfgang Rave:
> Alfred Flaßhaar schrieb am Mittwoch, 21. September 2022 um 15:38:18 UTC+2:

Korrektur Tipfehler:
>> Die Gleichung 2*x^2 - _17_*y^2 = 1 habe ich völlig anders ohne ...

(...)

Gruß, Alfred

[Wolfgang Rave]

Wolfgang Rave schrieb am Mittwoch, 21. September 2022 um 18:31:58 UTC+2:

> Pellsche Resolvente sagt mir gar nix. Bin aber auch nur Zth-Amateur ...!

> euer Wolfgang.

hi all,
Pellsche Resolvente is ja ganz einfach.
Gesucht (x,y) für x^2 - Dy^2 = a =/= 1, D, a € |N gegeben,
dann ist x^2 - Dy^2 = 1 die Pellsche Resolvente.
Ich hätt gedacht, das wär komplizierter ... siehe
https://en.wikipedia.org/wiki/Pell%27s_equation "Generalized Pell".
Manchmal ist sogar die Mathe nett und freundlich zu mir ...

Wolfgang.

[neu...@tuhh.de]

Sehr schöner Artikel. Macht mir die Antworten auf meine Fragen klarer
- auch der Hinweis auf die Algebraische Zahlentheorie.

Auch, daß die Lösungen von x² -Dy²= n, genauer x/y gegen Wurzel(D) konvergiert, und mit (x,y) auch die Matrix
( x y )^n
(ny x) für n=1,2,3,... Lösungen liefert.
Ist (x,y) "die kleinste Lösung", so liefern die Potenzen _alle_ anderen!
(Es gibt nur für ausgewählte n Lösungen - eine Frage wäre noch welche? Warum?)

Danke Wolfgang.
Zum Spielen finde ich http://www.schaffenroth.de/Mathematik/Pell.html auch recht schön!

VG SiggiN.

P.S.: Bitte, was ist denn ein "Zth-Amateur". ;-)

[Wolfgang Rave]

neu...@tuhh.de schrieb am Donnerstag, 22. September 2022 um 20:01:23 UTC+2:

> > Pellsche Resolvente is ja ganz einfach.
> > Gesucht (x,y) für x^2 - Dy^2 = a =/= 1, D, a € |N gegeben,
> > dann ist x^2 - Dy^2 = 1 die Pellsche Resolvente.

> Sehr schöner Artikel. Macht mir die Antworten auf meine Fragen klarer
> - auch der Hinweis auf die Algebraische Zahlentheorie.

Gerne doch. Hab selber viel von wiki gelernt.

> (Es gibt nur für ausgewählte n Lösungen - eine Frage wäre noch welche? Warum?)

Soweit ich das sehe, nennt Schaffenroth mein a von oben n (Konfusion!).
Und Pell kann nicht alle Werte annehmen. Hatten wir ja schon:
2x^2 - 17y^2 = 1 liefert (mit Kettenbruch) -9, 1, -9, 2 mit Periode 4.

> Danke Wolfgang.
> Zum Spielen finde ich http://www.schaffenroth.de/Mathematik/Pell.html auch recht schön!

Ich hab mir 'n Excel-Sheet gebastelt, mit dem ich alle bis D=10000 durchgeixt hab.
Fürn Hausgebrauch reicht das.

> VG SiggiN.
>
> P.S.: Bitte, was ist denn ein "Zth-Amateur". ;-)

Ein Zahn-Thesen-Amateur, äh - Zahlentheorie-Amateur ;-)

herzlich, Wolfgang.