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