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

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.

• 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$. – tkf Jul 13 at 1:20
• @tkf: would you like to develop that into an answer? – J. W. Tanner Jul 13 at 1:49
• @J.W.Tanner Done – tkf Jul 13 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$$

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