A conjecture on $\phi(n)$

Question

Let $\phi(n)$ denote the Euler totient function of $n $.
Then let $N$ be a number such that $\phi(N)$ divides $N$ . Also let $I_1= \frac{N}{\phi(N)}$ which is defined as the "Second order Index of Beauty of $N$ ".

Then prove that - For every number $I_1$ there exists a number $N$ such that $I_1$ is the second order index of beauty of $N$.

Answer 1

I am sorry, but the conjecture is really false: In fact, there are no other integer values for $N/\varphi(N)$ other then $1,2,3$. Reason:

The function $\varphi(N)$ is a multiplicative number-theoretic function. Let $N = \prod p_i^{k_i}$ with pairwise distinct primes $p_i$ dividing $N$, then $$\frac{N}{\varphi(N)} = \frac{\prod p_i^{k_i}}{\prod (p_i-1)p_i^{k_i-1}} = \frac{\prod p_i }{ \prod (p_i-1)}.$$

Now compare prime factors of the numerator and the denominator:

• If $N$ is divisible by $3$, then there is a $2$ in the denominator, canceling the only remaining $2$ in the numerator. This means that there cannot be another prime factor of $N$ other than $2,3$. So $N/\varphi(N)=3$ is the only integer value in this case, obtained by any $N$ of the form $2^k3^j$.
• Suppose $N$ is divisible by a prime $>3$ and let $p$ be the lowest such prime. Then there is $p-1$ in the denominator which must be canceled by primes in the numerator lower than $p$. But as we have already ruled out $3$, there is only a single $2$ in the numerator remaining as a possible factor of $p-1$, a contradiction.
• The only remaining value is $N/\varphi(N) = 1$ for $n=1$ and $N/\varphi(N) = 2$ for $N = 2^k$.

---

EDIT

By the way, as this was discussed alongside: Here is my recommendation for calculation of many values of $\varphi(N)$: use Sieves.

N = 10**8
BeautyIndex = set([1])
PHI = numpy.arange(N)

for i in xrange(2,N):
   if PHI[i]==i:#i is prime
     PHI[i::i]*=i-1
     PHI[i::i]/=i
   if i%PHI[i]==0:
     BeautyIndex.add(i)
print BeautyIndex

Answer 2

Not an answer, but this won't work as a comment. Here's the requested code to have a look-see in a slow, brute force way in Python.

def totient(n):
  if n == 1: return 1
  return sum(d * mobius(n / d) for d in range(1, n+1) if n % d == 0)
def mobius(n):
  result, i = 1, 2
  while n >= i:
    if n % i == 0:
      n = n / i
        if n % i == 0:
          return 0
      result = -result
    i = i + 1
  return result

results = set() #sets store only unique items, so the output is cleaner

for n in range(1,[large number]):
  if float(n)/float(totient(n))==float(n/totient(n)): #integer check
    results.add(n/totient(n))

for item in results:
  print str(item) #shows what we got

Update: Up to $100000$, we get $\{1,2,3\}$.