4007 , 6007 , 9007 , 10007 , 12007 , 13007 , 16007 , 24007 , 36007 , 45007 , 61007 , 64007 , 78007 , 82007 , 88007 , 90007 , 94007 , 97007 , >>>Total= 18
All the above integers between 1000 and 100,000 end in 007 and are Prime Numbers. You may take any one of them and subtract 1.
Example: m = 9007 - 1 =9006. Any or ALL "n" between 1 and 9006 inclusive are relatively prime to m, or 9007 in this particular case. This comes from the definition of "Euler's Totient Function", or sometimes called "Euler's Phi Function"
I hope that this is what your Math Teacher had in mind when he/she posed this question.