0

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?

ClimbingTheCurve
  • 135
  • 3
    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. – InequalitiesEverywhere Jan 01 '19 at 12:48

1 Answers1

2

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

PrincessEev
  • 43,815
  • Should you not mention that your final claim is the Fundamental Theorem of Arithmetic?

    https://en.wikipedia.org/wiki/Fundamental_theorem_of_arithmetic

     –  Jan 08 '19 at 05:07