Satz RELPRIME ist in P

Einfache Sprache

Da eine Lösung nach dem Versuch-und-Irrtum-Prinzip auszuprobieren muss alle möglichen Teiler ausprobieren und akzeptiert wenn mindestens einer größer 1 ist. Da aber die Anzahl an Zahlen die durch eine binäre Zahl repräsentiert werden können exponentiell mit der Länge der Zahl wächst, würden man exponentielle Laufzeit benötigen um alle möglichen Teiler zu testen. Also nutzen wir den Euklidischer Algorithmus

Def. Satz RELPRIME ist in P