Question

show that we can easily factor when we know that n is the product of two primes, p and q, and we know the value of $\mathbf{(}\mathbf{p}\mathbf{‐}\mathbf{1}\mathbf{)}\mathbf{(}\mathbf{q}\mathbf{‐}\mathbf{1}\mathbf{)}$

Short answer

Since we know $\mathbf{n}$androle="math" localid="1668667931552" $\mathbf{(}\mathbf{p}\mathbf{‐}\mathbf{1}\mathbf{)}\mathbf{(}\mathbf{q}\mathbf{‐}\mathbf{1}\mathbf{)}$, we can determine $\mathbf{x}\mathbf{=}\mathbf{p}\mathbf{+}\mathbf{q}$and then $\mathbf{p}$can be determined using the quadratic formula to solve ${\mathbf{p}}^{\mathbf{2}}\mathbf{‐}\mathbf{xp}\mathbf{+}\mathbf{n}\mathbf{=}\mathbf{0}$, while $\mathbf{q}$can then be obtained using$\mathbf{n}\mathbf{=}\mathbf{pq}$

Step-by-step solution

Step 1

Let us assume that$\mathbf{n}$ is a positive integer that is the product of two primes $\mathbf{p}$and$\mathbf{q}$

$\mathbf{n}\mathbf{=}\mathbf{pq}$

We have also been given the value of $\left(p‐1\right)\left(q‐1\right)$

$\mathbf{(}\mathbf{p}\mathbf{-}\mathbf{1}\mathbf{)}\mathbf{(}\mathbf{q}\mathbf{-}\mathbf{1}\mathbf{)}\mathbf{=}\mathbf{pq}\mathbf{-}\mathbf{p}\mathbf{-}\mathbf{q}\mathbf{+}\mathbf{1}\mathbf{=}\mathbf{n}\mathbf{-}\mathbf{p}\mathbf{-}\mathbf{q}\mathbf{+}\mathbf{1}\mathbf{=}\mathbf{n}\mathbf{-}\mathbf{(}\mathbf{p}\mathbf{+}\mathbf{q}\mathbf{)}\mathbf{+}\mathbf{1}$

However, we know both andand thus we can calculate$\mathbf{p}\mathbf{+}\mathbf{q}$ as

$\mathbf{p}\mathbf{+}\mathbf{q}\mathbf{=}\mathbf{-}\mathbf{\left(}\mathbf{\right(}\mathbf{p}\mathbf{-}\mathbf{1}\mathbf{\left)}\mathbf{\right(}\mathbf{q}\mathbf{-}\mathbf{1}\mathbf{)}\mathbf{-}\mathbf{n}\mathbf{-}\mathbf{1}\mathbf{)}\mathbf{=}\mathbf{n}\mathbf{+}\mathbf{1}\mathbf{-}\mathbf{(}\mathbf{p}\mathbf{-}\mathbf{1}\mathbf{)}\mathbf{(}\mathbf{q}\mathbf{-}\mathbf{1}\mathbf{)}$

Step 2

Let $\mathbf{x}\mathbf{=}\mathbf{p}\mathbf{+}\mathbf{q}$. we then note $\mathbf{p}\mathbf{=}\mathbf{x}\mathbf{‐}\mathbf{q}$ or equivalently $\mathbf{n}\mathbf{=}\mathbf{pq}\mathbf{=}\mathbf{xp}\mathbf{‐}{\mathbf{p}}^{\mathbf{2}}$. However, thus then implies that the following equation needs to hold .

${\mathbf{p}}^{\mathbf{2}}\mathbf{‐}\mathbf{xp}\mathbf{+}\mathbf{n}\mathbf{=}\mathbf{0}$

We can then determine the root $\mathbf{p}$using the quadratic formula and we then use$\mathbf{q}\mathbf{=}\mathbf{n}\mathbf{/}\mathbf{p}$ to determine $\mathbf{q}$ (once$\mathbf{p}$ is known).