Xrfgtjtk

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[30] (this is 8) and indeed, list[[;;8]] + 30 coincides with list[[9;;16]]. How to continue from here?

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[20]]

{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[16]

{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][[1]]

                             ]

f[m_, i_] := (

    m*#[[1]] + 

      Select[Range[m], GCD[#, m] == 1 &][[ #[[2]] ]] 

  )& [ 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*#[[1]] + fTable[m][[#[[2]] ]]

  )& [ 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.