# How to generate a random, relatively prime number to p?

I'm sorry if this is an obvious question, but I'm a newbie and googling didn't help me much.

Is there a way in Mathematica to generate a number q coprime with p without resorting to do it "by hand" by iterating over a list of random numbers and using CoprimeQ?

I see how the likelihood of hitting a coprime soon is pretty good, but I wonder if there is a cleaner, or, if you want, more Mathematica-like way to do it.

Thank you very much.

• just FYI the brute force approach (While[ ! CoprimeQ[n , i = RandomInteger[n]]]; i) is much faster than the "more elegant" answers.. – george2079 Apr 15 '15 at 15:08
• @george2079 hey, I like more elegant answer! – rcollyer Apr 15 '15 at 18:59

This is a straightforward function generating a random coprime number less than given natural number x.

cpr[x_Integer]/; x > 1 :=
RandomChoice @ Pick[ Range[x], CoprimeQ[ x, Range[x]]]


e.g.

cpr

79


However if we are to deal with larger numbers the given definition is not very convenient therfore it is reasonable to provide another definition yielding a random coprime between k and m e.g.

cpr[x_Integer, k_Integer, m_Integer] /; x > m > k > 1 :=
RandomChoice @ Pick[ Range[k, m], CoprimeQ[ x, Range[k, m]]]


for a choice between k and m

e.g.

cpr[32059725, 21172781, 25565647]

21921206


If one chooses an appropriate range there are always some coprimes unless k and m are too close.

• I believe this is a solution that the OP has specifically excluded in their question. Better if we can do it without having to generate a list of candidates and only after that verify whether they are coprime or not. – Oleksandr R. Apr 15 '15 at 11:30
• @OleksandrR. The provided solution is quite good and very Mathematica-like one. The OP as a newbie excludes iterating over a list of random numbers and then using CoprimeQ. There is no iteration, no random list, just a range of numbers and simply CoprimeQ for which there is no better substitution. Just a reliable solution, if you can see a better one, clarify what you mean. I guess you might have suggested another mathematical approach if it had existed but I susspect it hadn't. Unless you find the solution by rcollyer better, however frankly I don't. – Artes Apr 16 '15 at 13:25

Using the definition of coprime, it is straightforward to construct a function that will do as you ask.

Clear[randomCoprime];
randomCoprime[n_Integer, k_Integer : Automatic] :=
Block[{count, maxP, factors, allowedF},
maxP = PrimePi@Sqrt@n;
factors = PrimePi@FactorInteger[n][[All,1]];
count = If[k===Automatic, RandomInteger[{2, maxP}], k];
allowedF = Complement[Range[2,maxP], factors];
Times@@Prime[RandomChoice[allowedF, count]]
]


It works by indexing the prime factors of n via PrimePi, generating a list of allowed prime indices, and then randomly choosing from that list. The final number is reconstructed using Prime. In the function, k determines the number of coprime factors chosen, and it will be randomly determined, if not specified.