Find the primes $p$ and $q$ if $n = pq = 14647$ and $\phi(n) = 14400$

I am having a hard time solving this question since I am new to this topic, any help would be appreciated. Thank you for your time.

  • 8
    $\begingroup$ You need to use $\phi(n)=(p-1)(q-1)$. Now find $p+q$. If you know the sum of two numbers is $a$, and the product is $b$, then the numbers will be the roots of the quadratic equation $x^2-ax+b$. $\endgroup$
    – tkf
    Jul 13 '20 at 1:20
  • $\begingroup$ @tkf: would you like to develop that into an answer? $\endgroup$ Jul 13 '20 at 1:49
  • 1
    $\begingroup$ @J.W.Tanner Done $\endgroup$
    – tkf
    Jul 13 '20 at 2:10

This is a very common question on cryptography modules. The method you are expected to use is as follows: \begin{eqnarray*}\phi(n)=(p-1)(q-1)&=&pq-(p+q)+1\\n&=&pq\end{eqnarray*}

Thus you just need to work out $m=n-\phi(n)+1=p+q$.

Now you know the sum of $p$ and $q$ as well as their product. Thus $$(x-p)(x-q)=x^2-mx+n.$$

To find $p,q$ you just need to solve the quadratic equation:$$x^2-mx+n=0.$$

The two roots will be $p,q$.


As $7=1\cdot7=3\cdot9$


$$pq=(10a+1)(10b+7)$$ or $$pq=(10c+3)(10c+9)$$


Now $(5b+3,5)=1\implies5$ must divide $a,a=5e$(say)


The factors of $144$ are $1,2,3,4,6,8,9,16,18,24,36,48,72,144$

which are respectively $\equiv1,2,3,4,1,3,4,1,3,4,1,3,2,4$

So, $5b+3\in[3,8,18,48]$

$\implies q=10b+7\in[7,17,37,97]$

Can you check $p=14647/q$ for prime values

Clearly $$14400\ne(10c+3-1)(10d+9-1)$$ for Integers $c,d$