Abstract algebra help please?

Question

Let's say an integer n satisfies φ(n) = 1000. What are all the primes that might possibly divide n?

Answer 1

phi(n) = n(1-1/p)....(1-1/z) where the primes in n are
p,...,z. Then n(p-1)...(z-1) = 1000p...z. Set
k=n/(p...z) an integer. Then k(p-1)...(z-1) = 1000. If k=1
we must factor 1000=(p-1)(q-1)...(z-1) where each factor is 1 less than a prime. Trying this for only two factors gives
1000=2*500=4*250=5*200=8*125=10*100=20*50=25*40
Out of these we have the pairs (2,500),(4,250),(10,100)
which give primes 3,501,5,251,11,101. More factors
reduces to the primes given as you may check. If k=2
then we factor 500 and no new primes appear and similarly
for k=2,4,5,8,....,k|1000. So n can have the primes
3,5,11,101,251,501 and only these.

Answer 2

first, since sqrt(1000)<32, you don't need to go beyond 31. The only primes are 2 and 5.