Subject: Re: RE: Finding a relative prime
- To: mathgroup at smc.vnet.net
- Subject: [mg19756] Subject: [mg19756] [mg19725] Re: [mg19694] RE: [mg19682] Finding a relative prime
- From: Ranko Bojanic <bojanic at math.ohio-state.edu>
- Date: Wed, 15 Sep 1999 03:53:06 -0400
- Organization: Ohio State University
- Sender: owner-wri-mathgroup at wolfram.com
Timur Tabi,timur at tabi.org 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?
There was a very lively and interesting discussion of this problem in
the MathGroup.
It is clearly irrelevant here whether p is a prime or not. So we can
reformulate the problem
as follows: given an integer n >2, select at random an integer k < n
such that k is relatively
prime to n.. A simple solution , which will insure that the numbers are
selected with equal
probability, is to find the rpLst of all numbers k < n which are
relatively prime to n and
then to select a random element of that list with
rpLst[[Random[Integer,{1,Length[rpLst}]]]
The main problem is, consequently, to find the most efficient way to
construct the list.
of integers < n and relatively prime to n.An immediate candidate is the
function
relPrimes[n_] = Select[Range[n],GCD[#,n]==1&];
This function clearly cannot be very fast for large values of n because
it has to examine
every element of the list Range[n].
relPrimes[100000];//Timing
{17.0333 Second,Null}
A faster function can be constructed by using Eratosthenes Sieve and the
fact that an
integer < n is relatively prime to n if it is not divisible by any prime
divisor of n. The
list of prime divisors of n is obtained by
pdLst[n_]:=First[Transpose[FactorInteger[n]]
If d is a prime divisor of n, then
Complement[Range[n], d Range[n / d]]
is a list of numbers between 1 and n which are not divisible by d.We
have to take all these
lists, for all prime divisors of n, and their intersection will be then
the list of all numbers
k<n which are relatively prime to n.
It is now easy to see that the rpLst of integers < n and relatively
prime to n can be defined
as follows:
rpLst[n_] :=
Module[{g=Complement[Range[n],# Range[n / #]]&,
pLst=First[Transpose[FactorInteger[n]]]},
Apply[Intersection,Map[g,pLst]]]
With this function we have
rpLst[100000];//Timing
{4.11667 Second,Null}
Finally, a list of 1000 randomly selected and uniformly distributed
integers < 100 and
relatively prime to 100 can be defined by
aLst=rpLst[100];
Table[aLst[[Random[Integer,{1,Length[aLst]}]]],{1000}]
Ranko Bojanic
bojanic at math.ohio-state.edu