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
- Reply-to: fransm at win.tue.nl
- 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