Natürliche Zahl in zwei Quadratzahlen zerlegen

Manuelito

Hallo,

ich muss natürliche Zahlen in zwei Quadratzahlen zerlegen (das geht bei den Zahlen, die ich hab) nur gibt es eine Formel dafür?

Formeln für die Anzahl der möglichen Zerlegungen bzw. zum Überprüfen, ob die Zahl in zwei Quadratzahlen zerlegbar ist, hab ich zur Genüge, aber gibt es auch Formeln, um die beiden Zahlen auszurechnen?

Grüße,
Manuelito

was du meinst ist wurzel ziehen oder ?
suchst nen wurzel algorithmus ?

Was meinst du mit "zerlegen"?

n = a^2 + b^2 oder n = a^2 * b^2 oder irgendwas ganz anderes?

for (int i = 0; i <= sqrtf(n); ++i)
  if (isSqr(n - i*i))
    cout << n << " = " << i << "^2 + " << n-i*i << "^2\n";

pumuckl

Tipp schrieb:

for (int i = 0; i <= sqrtf(n); ++i)
  if (isSqr(n - i*i))
    cout << n << " = " << i << "^2 + " << n-i*i << "^2\n";

Ist ziemlich falsch, da $i^2+(n-i^2)^2 \neq n$ , was aber das ist was du da stehn hast.

Jester

naja, nur die ausgabe ist falsch. die überprüfung ist immerhin richtig.

for (int i = 0; i <= sqrtf(n); ++i)
  if (isSqr(n - i*i))
    cout << n << " = " << i << "^2 + " << (int)sqrtf(n-i*i) << "^2\n";

Manuelito

Ich suche was in der Form n = a^2 + b^2. Aber kein Programm, das alles durchprobiert, sondern eine Formel zum ausrechnen.

Ribosom

Manuelito schrieb:

Ich suche was in der Form n = a^2 + b^2. Aber kein Programm, das alles durchprobiert, sondern eine Formel zum ausrechnen.

Ohne Einschränkung n prim. Zerlege n in \mathbb{Z}[i] ein Produkt von zwei Primidealen (Diese sind Hauptideale). Dazu musst du X^2 + 1 modulo p faktorisieren <=> suche Quadratwurzel von -1 mod p. Dazu gibt es z.B. den Shanks-Tonelli-Algorithmus. Wenn X^2 - 1 = (X - a)(X + a) deine Faktorisierung ist, dann sind (i - a, p) und (i + a, p) deine gesuchten Ideale. Mit dem euklidischen Algorithmus kannst du den ggT von i +- a und p in \mathbb{Z}[i] berechnen und somit eine Darstellung als Hauptideal (x + iy) mit x,y ganzzahlig bestimmen. Dann ist p = x^2 + y^2.

EDIT: Nur aus Neugierde, wozu brauchst du das?

Jester

Ribosom schrieb:

Ohne Einschränkung n prim.

Da steh ich grad auf der Leitung, wieso?

Ribosom

Jester schrieb:

Ribosom schrieb:

Ohne Einschränkung n prim.

Da steh ich grad auf der Leitung, wieso?

Wenn n = x^2 + y^2, m = u^2 + v^2 Summe zweier Quadrate sind, dann hat man auch die Darstellung von nm, indem man (x + iy)(u + iv) = (xu - yv) + (xv + yu)i rechnet und dann (xu - yv)^2 + (xv + yu)^2 = nm erhält.

MasterCounter

was sind ideale?

Ribosom

http://de.wikipedia.org/wiki/Ideal_(Ringtheorie)

MasterCounter

Ja schon, nur da scheiterts schon an dem Begriff "Zahlenring" ^^

Ribosom

Dann wär vielleicht der Thread was für dich: http://www.c-plusplus.net/forum/viewtopic-var-t-is-203454.html

Manuelito

@ Ribosom: Danke für deine Antwort, aber um ehrlich zu sein, versteh ich überhaupt nichts. Da wird ausprobieren dann wohl der bessere Weg sein

.filmor

http://en.wikipedia.org/wiki/Shanks-Tonelli_algorithm
Damit erhältst du (wenn ich die Zerlegung richtig verstanden habe (ich kenne zumindest die verwendeten Begriffe ;)) und p := n ist, man korrigiere dich gegebenenfalls) eine Zahl R für die in C++-Notation gilt: (R * R) % p == p - 1

Nun ist die Behauptung, dass ggT(R + i, p) und ggT(R - i, p) die gesuchten Zahlen a, b sind. Das i ist dabei die imaginäre Einheit, den ggT berechnest du mit dem euklidischem Algorithmus (der praktischerweise auch in |Z[i] funktioniert, implementier ihn vielleicht einfach erstmal allgemein).

Du musst also zwei Algorithmen bauen, den Bereich dazwischen füllen geht auch. Und schneller als ausprobieren sollte das schon sein (zumindest wenn n ausreichend groß ist) ;).