Let n be a positive integer. Prove that there exists a positive integer m > 1000 with the following two properties: m’s last 3 digits are 007, and m is relatively prime to n.

SpicyP Aug 17, 2020

#1**0 **

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.

Guest Aug 17, 2020