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

```

• Prev by Date: Re: InputForm Query
• Next by Date: Re: Don't want to calculate scalar product
• Previous by thread: Re: Where's the Speed?
• Next by thread: Re: Subject: Re: RE: Finding a relative prime