# Factoring a number $p^a q^b$ knowing its totient

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.

-

Without loss of generality we can assume that $p<q$. 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.

-
Thank you, I was hoping there's some way to avoid the initial case guesswork but I suppose this will have to do. –  poe123 May 12 '12 at 12:21
@poe123, if you knew about this method, you could have said so. And waited for somebody to suggest a clever trick avoiding the verification step :-) No harm done, though! –  Jyrki Lahtonen May 12 '12 at 12:25
Once 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$. –  Zander May 14 '12 at 17:15