Re: Re: Finding a relative prime (corrected)

*To*: mathgroup at smc.vnet.net*Subject*: [mg19723] Re: [mg19697] Re: [mg19682] Finding a relative prime (corrected)*From*: "Andrzej Kozlowski" <andrzej at tuins.ac.jp>*Date*: Mon, 13 Sep 1999 02:40:56 -0400*Sender*: owner-wri-mathgroup at wolfram.com

As so often happens, looking at my own message I noticed a silly bug. The correct code should have been of course: randompick[q_?PrimeQ] := Select[Range[2, q - 1], GCD[q, #] == 1 &][[Random[Integer, {1, EulerPhi[q-1] - 1}]]] (Note that for a prime q we have EulerPhi[q]==q-1) Andrzej Kozlowski Toyama International University JAPAN http://sigma.tuins.ac.jp http://eri2.tuins.ac.jp ---------- >From: "Andrzej Kozlowski" <andrzej at tuins.ac.jp> To: mathgroup at smc.vnet.net >To: mathgroup at smc.vnet.net >Subject: [mg19723] [mg19697] Re: [mg19682] Finding a relative prime (corrected) >Date: Sat, 11 Sep 1999 16:36:04 -0400 > > Sorry, I answered to quickly and misunderstood your question. Of course you > want a number relatively prime to q , not a prime number. So the correct > code is: > > randompick[q_?PrimeQ] := > Module[{l}, (l = Select[Range[2, q - 1], GCD[q, #] == 1 &])[[Random[ > Integer, {1, Length[l]}]]]] > > E.g: > > In[23]:= > randompick[Prime[1000]] > Out[23]= > 552 > > Actually one can simplify this a bit by using th ebuilt in function > EulerPhi, where EulerPhi[n] is the number of positive integers less than n > which are relatively prime to n. Then the code becomes: > > randompick[q_?PrimeQ] := > Select[Range[2, q - 1], > GCD[q, #] == 1 &][[Random[Integer, {1, EulerPhi[q] - 1}]]] > > > > -- > Andrzej Kozlowski > Toyama International University > JAPAN > http://sigma.tuins.ac.jp > http://eri2.tuins.ac.jp > > > ---------- >>From: Timur Tabi <nospam_timur at tabi.org> To: mathgroup at smc.vnet.net >>To: mathgroup at smc.vnet.net >>Subject: [mg19723] [mg19697] [mg19682] Finding a relative prime >>Date: Thu, Sep 9, 1999, 3:19 PM >> > >> 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? >> >> -- >> Remove "nospam_" from my email address when replying >> Timur "too sexy for my code" Tabi, timur at tabi.org >> >> >> Sent via Deja.com http://www.deja.com/ >> Share what you know. Learn what you don't. >> >> >