Zitat von
Flocke:
Zitat von
Dr.Hackstable:
a,b,x,y seien 512-bit Zahlen die keinen ggt haben
@Hagen: Ich habe deinen Beitrag schon verstanden. Ich wollte nur darauf hinweisen, dass er das bei teilerfremden Zahlen nicht anwenden kann (-> keine gemeinsamen Primfaktoren -> keine gemeinsamen Basen).
wenn der ggT() = 1 ist dann heist dies nicht das zwangsläufig bei der Primfaktorzerlegung der Potenzen nicht gemeinsamme Basen existieren. Und selbst wenn dann heist dies dann nur das in der "subtrahierten" Primzahlfaktorization diese nicht gemeinsammen Basen wieder auftauchen. Entweder als b^x oder b^-y.
Es muß sogar so sein, da es ansonsten ja für Primzahlfaktoren[a^x] / Primzahlfaktotren[b^y] = z, für Z keine Primzahlfaktorenzerlegung existieren könnte. Und dies ist unmöglich da wir Potenzen vor uns haben. Im schlechtesten Falle ist a und b eine Primzahl selber und die Primzahlzerlegung wäre a^x = a^x und b^y = b^y, dann wäre die Zerlegung unseres rationalen Produktes exakt a^x * b^-y. Unsere Zahl Z zerlegt sich also in die Primzahlen a und b mit den Primzahlexponenten a^x * b^-y.
Gruß Hagen