RE: Finding a relative prime
- To: mathgroup at smc.vnet.net
- Subject: [mg19694] RE: [mg19682] Finding a relative prime
- From: "Ersek, Ted R" <ErsekTR at navair.navy.mil>
- Date: Sat, 11 Sep 1999 16:36:02 -0400
- Sender: owner-wri-mathgroup at wolfram.com
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, 2) k is relatively prime to p-1. ------------------------ This should work: PickNumber[p_?PrimeQ]:= Module[{tst,k}, While[tst=!=1, k=Random[Integer,{2,p-2}]; tst=GCD[k,p-1] ]; k ] However, when p=2,3,5,7 there is only one integer less than (p-1) that is relatively prime to (p-1), and that doesn't allow for a very random outcome. -------------------- Regards, Ted Ersek For Mathematica tips, tricks see http://www.dot.net.au/~elisha/ersek/Tricks.html