MathGroup Archive 1999

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

Search the Archive

Subject: Re: RE: Finding a relative prime

  • To: mathgroup at
  • Subject: [mg19756] Subject: [mg19756] [mg19725] Re: [mg19694] RE: [mg19682] Finding a relative prime
  • From: Ranko Bojanic <bojanic at>
  • Date: Wed, 15 Sep 1999 03:53:06 -0400
  • Organization: Ohio State University
  • Sender: owner-wri-mathgroup at

Timur Tabi,timur at 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
> 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


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

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

     {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


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 / #]]&,

With this function we have
             {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


Ranko Bojanic
bojanic at

  • 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