Take the 2-minute tour ×  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.  share|improve this question add
comment  1 Answer  up vote 5 down vote accepted  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}{