We are given: $n=p^aq^b$ and $\phi(n)$, where $p,q$ are prime numbers. I have to calculate the $a,b,p,q$, possibly using computer for some calculations, but the method is supposed to be symbolically valid and proper. I know that $\phi(n)=p^{a-1}q^{b-1}(p-1)(q-1)$, but I dont know what can I deduct from this.
Factoring a number $p^a q^b$ knowing its totient
1 Answers
Without loss of generality we can assume that $p. I would first compute the greatest common divisor of $n$ and $\phi(n)$, $m=\gcd(n,\phi(n))$. There are two possibilities.
1) $m=p^{a-1}q^{b-1}$. This happens, if $p$ is not a factor of $q-1$. In this case we can calculate $ \frac{n}{m}=pq,\qquad\text{and}\qquad \frac{\phi(n)}{m}=(p-1)(q-1)=pq-(p+q)+1. $ In this case we know $r=p+q$ and $s=pq$, and can solve the primes $p$ and $q$ as the roots of the quadratic equation $ 0=(x-p)(x-q)=x^2-(p+q)x+pq=x^2-rx+s. $
2) $m=p^aq^{b-1}$. This happens, if $p$ is a factor of $q-1$. This time $ \frac{n}{m}=q,\qquad\text{and}\qquad\frac{\phi(n)}{m}=\frac{(p-1)(q-1)}p. $
I think that is possible to build a method from these bits alone. I would assume that we have the first case, and then check that it works in a separate verification step. The roots of the quadratic need to be integers, and we can keep on dividing $n$ with the roots to verify that the number $n$ is, indeed, of the form $p^aq^b$. If something goes wrong, then we must have case 2. This time we know $q$ directly, and can solve for $p$ from the equation $ \frac1{q-1}\cdot\frac{\phi(n)}{m}=\frac1{q-1}\cdot\frac{(p-1)(q-1)}p=\frac{p-1}p=1-\frac1p, $ because the LHS is known.
Undoubtedly there are alternative ways of exploiting these bits. The key is to compute $m$ first.
-
0Once you have $t=n/m$ you can repeatedly divide it out of $n$ to get a power of $p$ or $q$ alone. Write $n=t^ku$, then if $u=1$ it's case 1) with $a=b$, otherwise in case 1) $\gcd(t,u)$ is $p$ or $q$, in case 2) $\gcd(t,u)$ is 1 and $t=q$. – 2012-05-14