1
$\begingroup$

If we know that $n = 1363$ and $φ(n) = 1288$, how can we factor $n$?

New contributor
mariohez is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
$\endgroup$
1
  • $\begingroup$ For example by repeatedly trying all possible factors of $n$. $1363 = 29 \cdot 47$. $\endgroup$ – Steven 2 days ago
2
$\begingroup$

If $n$ is the product of two distinct primes, say $n = pq$, then $\varphi(n) = (p-1)(q-1) = pq-(p+q)+1$. Therefore given $n$ and $\varphi(n)$ you can determine both $pq$ and $p+q$. By solving a quadratic equation, you can find both $p$ and $q$.

$\endgroup$

Your Answer

mariohez is a new contributor. Be nice, and check out our Code of Conduct.

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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