Re: Re: Finding a relative prime

• To: mathgroup at smc.vnet.net
• Subject: [mg19757] Re: [mg19704] Re: Finding a relative prime
• From: "Frans Martens" <fransm at win.tue.nl>
• Date: Wed, 15 Sep 1999 03:53:06 -0400
• Sender: owner-wri-mathgroup at wolfram.com

```Hello,

Timur Tabi wrote

I'm using Mathematica 3.0 for the Mac, and I'm trying to figure out how
to get it to pick a random number that is relatively prime to another
number, p-1, where p is prime.  In other words, pick a random number k
such that 1) k is between 2 and p-1, and 2) k is relatively prime to p-1.
How can I do that in Mathematica 3.0?

Ken Levasseur used in his solution FixedPoint.

relprime[p_] :=
FixedPoint[Random[Integer, {2, p - 2}] &, p - 1,
SameTest -> ((GCD[p - 1, #2] == 1) &)]

You can also use a recursive function:

Clear[f];
f[p_] /; PrimeQ[p] && p > 3 :=
(If[GCD[#1, p - 1] === 1, #1, f[p]] & )[Random[Integer, {2, p - 2}]]

Frans Martens
Eindhoven University of Technology
Faculty of Mathematics and Computer Science
P.O.Box 513
5600 MB Eindhoven The Netherlands
Telephone -31402474280
Telefax -31402436685
E-mail fransm at win.tue.nl

```

• Prev by Date: RE: 3DPlots... Also, generalizations to nDPlots, n>3
• Next by Date: Special 3D Plots
• Previous by thread: Re: RE: Finding a relative prime