Services & Resources / Wolfram Forums
-----
 /
MathGroup Archive
1999
*January
*February
*March
*April
*May
*June
*July
*August
*September
*October
*November
*December
*Archive Index
*Ask about this page
*Print this page
*Give us feedback
*Sign up for the Wolfram Insider

MathGroup Archive 1999

[Date Index] [Thread Index] [Author Index]

Search the Archive

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.
>>
>>
> 


  • Prev by Date: Re: RE: Finding a relative prime
  • Next by Date: Re: Manipulating a list of pairs
  • Previous by thread: Re: Finding a relative prime (corrected)
  • Next by thread: Q: how do I get the TCP port number for $ParentLink