For any positive integer n, let d(n) denote the number of positive divisors of n; and let φ(n) denote the

Question

For any positive integer n, let d(n) denote the number of positive divisors of n; and let φ(n) denote the number of elements from the set {1, 2, · · · , n} that are coprime to n. (For example, d(12) = 6 and φ(12) = 4.) Find the smallest positive integer n such that d(φ(n)) = 2017.

I have arrived at the stage wherein p^2016=φ(n) What shall I do next? Why cannot p=1;φ(n)=1 and then n will be equal to 1. The answer is actually 2^2017

Answer 1

Just looking for patterns. It seems that there is often one value $n$ that gives $d(\phi(n)) = p$ where $n$ is a little smaller than the power of $2$ that works. However, this number $n$ is a Fermat prime or the product of Fermat primes. So, if you can prove that, you probably have it.

=================================

jagy@phobeusjunior:~$ grep "prime:   3" mse.txt | head -3
5 =  5   prime:   3
8 =  2^3   prime:   3
10 =  2 5   prime:   3
jagy@phobeusjunior:~$ grep "prime:   5" mse.txt | head -3
17 =  17   prime:   5
32 =  2^5   prime:   5
34 =  2 17   prime:   5
jagy@phobeusjunior:~$ grep "prime:   7" mse.txt | head -3
85 =  5 17   prime:   7
128 =  2^7   prime:   7
136 =  2^3 17   prime:   7
jagy@phobeusjunior:~$ grep "prime:   11" mse.txt | head -3
1285 =  5 257   prime:   11
2048 =  2^11   prime:   11
2056 =  2^3 257   prime:   11
jagy@phobeusjunior:~$ grep "prime:   13" mse.txt | head -3
4369 =  17 257   prime:   13
8192 =  2^13   prime:   13
8224 =  2^5 257   prime:   13
jagy@phobeusjunior:~$ grep "prime:   17" mse.txt | head -3
65537 =  65537   prime:   17
131072 =  2^17   prime:   17
131074 =  2 65537   prime:   17
jagy@phobeusjunior:~$ grep "prime:   19" mse.txt | head -3
327685 =  5 65537   prime:   19
524288 =  2^19   prime:   19
524296 =  2^3 65537   prime:   19

===============