n teilerfremd zu p

[curry-king]

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

[Daniel E.]

Irgendeine? Was willst Du denn damit?

Spontan hätte ich p-1 genommen, das stimmt fast immer.

[Jester]

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

[Windalf]

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;}