5
$\begingroup$

Edit: The quoted question addresses only numbers of the form $p^a q^b$, I asked a general question for arbitrary $n$.


If $n$ is a prime or a product of 2 primes then knowing its totient $\varphi(n)$ allows us immediately to find the prime factorization of $n$.

How about a general case? Does knowing $\varphi(n)$

  1. give us a way how to find the prime factorization of $n$,
  2. help as find a prime factor of $n$, or at least
  3. help at in finding any factor of $n$? (This turns out to be obvious.)
  • 3
    If $n$ is not square-free, then $gcd(n, \phi(n))$ is a non-trivial factor.2012-09-06
  • 1
    @RossMillikan The question you link deals with the case when $n=p^a q^b$. So it truly gives a partial answer to this one, but not to the general case when $n$ has 3 or more prime factors.2012-09-06
  • 0
    If http://en.wikipedia.org/wiki/Carmichael%27s_totient_function_conjecture is true, there are at least two numbers having same totient value.2012-09-06

3 Answers 3