Your attempt was not so far away from the solution:
In[1]:= Select[Range[2, 100], CoprimeQ[#, 100] &]
Out[1]= {3, 7, 9, 11, 13, 17, 19, 21, 23, 27, 29, 31, 33, 37, 39, 41, \
43, 47, 49, 51, 53, 57, 59, 61, 63, 67, 69, 71, 73, 77, 79, 81, 83, \
87, 89, 91, 93, 97, 99}
In[5]:= RandomChoice[Select[Range[2, 100], CoprimeQ[#, 100] &], 5]
Out[5]= {77, 99, 73, 9, 57}