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

Question

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.

Answer 1

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

So,

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

$$14400=10a(10b+6)\iff720=a(5b+3)$$

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

$144=e(5b+3)$

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$

Answer 2

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$.