0

An interesting question has come up to my attention, in particular what is the number of divisors of $φ(n)$, when given a natural number $n$? Where $φ$ quite unassumingly denotes Euler's Phi function. Now, I've noticed that this problem reduces to just finding $υ_p(φ(n))$, where $υ_p(m)$ denotes the largest power of an arbitrary prime divisor $p$ of $m$, since it is known that $$d(m)=\prod_{p|m}(υ_p(m)+1).$$ So, in essence, I'm asking what is the prime factorization of $φ(n)$ given the primitive analysis of n?

NOTE

This is also connected to finding the number of all possible orders modulo $n$. To be more specific, given an integer $a$ so that $gcd(a,n)=1$, how could we determine the number of all $ord_n(a)$. Therefore, observing that $ord_n(a)|φ(n)$, we have this number being equal to $d(φ(n))$.

EDIT/UPDATE

I scratched the previous comment, for the reason that an interesting result has come up to my attention, in particular if $p$ is prime and $α,β \in \mathbb Q$, then $υ_p(αβ)=υ_p(α)+υ_p(β)$. Therefore, $$υ_p(φ(n))=υ_p(n\prod_{p|n}( 1-\frac{1}{p} ))=υ_p(n)+\prod_{p|n}(υ_p(1-\frac{1}{p}))=υ_p(n)+\prod_{p|n}(υ_p(p-1)-1).$$ From this I noticed that if $n$ is even, then this dramatically simplifies to $υ_p(φ(n))=υ_p(n)$, thus matching the prime factorization of $n$.

  • Not quite sure what you want. But even if we have the prime factorization of $n$ , we cannot necessarily easily factor $\varphi(n)$. To determine the number of divisors of $\varphi(n)$ , we simply need the prime factorization of $\varphi(n)$. – Peter Dec 09 '23 at 07:20
  • @Peter Again, in essence, I'm asking about the prime factorization of $φ(n)$ in the general case. Also, I don't know if that is even possible to uncover, I'm just curious to know if it is. – Vaskara_GRek_O Dec 09 '23 at 12:35

0 Answers0