0
$\begingroup$

This may not be the best way to formulate the question but I am looking for a method to solve the following equation $d \cdot n'=n$ where $d, n', n \in \mathbb{N}$ and $n \neq1$ is known. How should I approach this problem? Are there guaranteed solutions?

$\endgroup$
1
  • 3
    $\begingroup$ You have basically asked if it is possible to find a factorization of $n$. If you forbid the trivial factorization of $1\cdot n = n$, then this problem is at least as hard as determining if $n$ is prime, and probably not harder than breaking the (multiprime) RSA encryption scheme. $\endgroup$ – InequalitiesEverywhere Jan 1 '19 at 12:48
2
$\begingroup$

They would be any two factors of $n$.

  • If $n$ is prime, then the numbers are $1,n$.
  • If $n=1$, $d=n'=1$.
  • If $n$ is composite, take any two factors $d, n'$ of $n$ such that $dn' = n$.

Solutions are indeed guaranteed for all $n \in \mathbb{N}$.

This follows from the facts that by definition the factors of a natural number are in turn also natural numbers, and that all numbers are prime, composite, or $1$.

$\endgroup$
1

Your Answer

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.