n teilerfremd zu p
-
Hi folks,
ich suche eine Zahl n, die teilerfremd zur Zahl p ist.
Kann mir jemand den Algo in Worten formulieren. Das würde mir echt weiterhelfen.Chiao
-
Irgendeine? Was willst Du denn damit?
Spontan hätte ich p-1 genommen, das stimmt fast immer.
-
Fast immer ist imho untertrieben.
Das funktioniert immer.nehmen wir an, wir haben einen Teiler k sowohl von p-1, als auch von p. Dann ist p-1 = 0 (mod k) und p = 0 (mod k), also auch die Differenz der beiden => 1 = 0 (mod k) das ist aber nur für k=1 der Fall. 1 ist aber kein echter Teiler.
MfG Jester
-
und wenns nicht immer p-1 sein soll kannst du ja auch einfach eine zufallszahl%p nehmen und checken ob diese teilerfremd ist... wenn ja hast du eine und wenn nein addierst du z.b. so lange 1 drauf bis es passt...
size_t gcd(size_t a, size_t b){return b?gcd(b,a%b):a;}