Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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 1

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}{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.

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.