mjhjmtu

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.