Forums Neueste Beiträge
 

Quadratzahlen und deren Kettenbr

20/10/2013 - 10:11 von Carsten Alexander | Report spam
Ich habe mich nàher mit der Kettenbruchentwicklung von Quadratzahlen
befasst. Dabei ist mir folgendes aufgefallen:

Teilt eine Zahl p die Zahl n, so hat der Kettenbruch für √(n² + p) die
Periode 2 und eine bestimmte Form. Ich habe mich unter

http://acamat.de/abacus/Kettenbruch.txt (UTF-8)

an einem Beweis versucht. Meine Fragen dazu sind jetzt:

1. Ist mein Beweis ausreichend und formal korrekt?
2. Ist der Umkehrschluss zulàssig?
2. Falls existent, wie heisst dieser Satz in der Literatur?
3. Wird dieser Satz bei einer Faktorisierungsmethode verwendet?

Die Kettenbruchentwicklung ist rechnerisch sehr günstig zu haben, weil
der Algorithmus lediglich die Addition verwendet. Die Kosten der
Quadrierung kann ich (noch) nicht einordnen, allerdings vermute ich, dass
es recht effiziente Verfahren gibt. Diese effiziente Methode
vorausgesetzt, sollte dieses Verfahren eigentlich günstiger als die
Probedivision sein.
 

Lesen sie die antworten

#1 Jan Fricke
20/10/2013 - 11:09 | Warnen spam
On 10/20/13 10:11, Carsten Alexander wrote:
Ich habe mich nàher mit der Kettenbruchentwicklung von Quadratzahlen
befasst. Dabei ist mir folgendes aufgefallen:

Teilt eine Zahl p die Zahl n, so hat der Kettenbruch für √(n² + p) die
Periode 2 und eine bestimmte Form. Ich habe mich unter


nàmlich (pq;[2q, 2pq]), wie Du richtig schreibst. (Ich habe die Periode
durch eckige Klammern gekennzeichnet.)


http://acamat.de/abacus/Kettenbruch.txt (UTF-8)

an einem Beweis versucht. Meine Fragen dazu sind jetzt:

1. Ist mein Beweis ausreichend und formal korrekt?


Ja, ist er. Im Prinzip rechnest Du ja die Kettenbruchentwicklung direkt aus.

Wenn man die Eindeutigkeit der Kettenbruchentwicklung benutzt, reicht es
auch aus, die Gleichung
x = pq + 1/(2q + 1/(pq + x))
zu lösen, was die (positive) Lösung √(n² + p) hat.

2. Ist der Umkehrschluss zulàssig?


Welcher Umkehrschluss?

2. Falls existent, wie heisst dieser Satz in der Literatur?


Das ist mir in dieser Form nicht als Satz in der Literatur bekannt, aber
sicherlich sind die Kettenbrüche der Lànge l für kleine l irgendwo
klassifiziert.

3. Wird dieser Satz bei einer Faktorisierungsmethode verwendet?


Sehr unwahrscheinlich, da sich nur sehr wenige Zahlen in der Form
N=(pq)²+p darstellen lassen. Das würde nàmlich bedeuten, dass für den
Primfaktor p von N die Zahl N-p eine Quadratzahl ist, was aber seeeehr
selten ist.


Viele Grüße Jan

Ähnliche fragen