# Generate numbers relatively prime with a given number

I am interested in a function such that f[m, i] = n where m, n are positive integers and n is the i-th number relatively prime with m.

Getting a sample of the possible outputs of f is straightforward. For example, let m = 30. Now we can use

list = 2 Range[0,29] + 1;
list = Pick[list, GCD[30, list], 1]
(*{1, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 49, 53, 59}*)


where I'm picking from odd numbers since m happens to be even. There should be a pattern in these numbers given by EulerPhi (this is 8) and indeed, list[[;;8]] + 30 coincides with list[[9;;16]]. How to continue from here?

• What is the range of $i$? – Αλέξανδρος Ζεγγ Dec 19 '18 at 13:52
• @ΑλέξανδροςΖεγγ Arbitrary positive integer. – Kiro Dec 19 '18 at 13:54

To find relative primes, I've found Complement to be generally faster than GCD or CoprimeQ.

RelativePrimes[m_Integer] :=
Complement[
Range[m - 1],
Apply[Sequence, Map[Range[#, m - 1, #] &, FactorInteger[m][[All, 1]]]]]


Your function f becomes the following.

f[m_, i_] :=
Block[{n = RelativePrimes[m], e = EulerPhi[m]},
n[[Mod[i, e, 1]]] + m * Quotient[i - 1, e]
]
SetAttributes[f,Listable]


Thus,

f[30,Range]


{1, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 49, 53, 59, 61, 67, 71, 73}

f[902,555]


1251

I give a naive implementation

ithCoprime[m_, i_] := Module[{coprimes, j = 1},
coprimes = {1};
While[Length[coprimes] < i,
j++;
If[CoprimeQ[m, j], AppendTo[coprimes, j]]
];
Last[coprimes]
]

ithCoprime[30, #] & /@ Range

{1, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 49, 53, 59}


Update

Here is a better version:

ithCoprime2[m_, i_] := Module[{j = 1, k = 1},
While[k < i, j++;
If[CoprimeQ[m, j], k++]
];
j
]


Update 2

Another version

ithCoprime3[m_, i_] := Module[{iterate, predicate, initial},
iterate = # + {1, Boole[CoprimeQ[m, First[#]]]} &;
predicate = Last[#] <= i &;
initial = {1, 1};
NestWhile[iterate, initial, predicate, 1, \[Infinity], -1][]
]

f[m_, i_] := (
m*#[] +
Select[Range[m], GCD[#, m] == 1 &][[ #[] ]]
)& [ QuotientRemainder[i, EulerPhi[m]] ]

RepeatedTiming[f[223 227, 4021987]]
(*  {0.058, 4057980}  *)


As long as m is not too big and you repeat ms, you can trade some memory for time.

fTable[m_] := fSmall[m] =
Select[Range[m], GCD[#, m] == 1 &];
f[m_, i_] := (m*#[] + fTable[m][[#[] ]]
)& [ QuotientRemainder[i, EulerPhi[m]] ]

RepeatedTiming[f[223 227, 4021987]]
(*  {0.0000110, 4057980}  *)


If you are repeating ms, but you still have too many different ms, discarding "old" fTables is a good idea.