Is a composite number n always either

  • a product of two coprimes (i.e. $n = n_1 \cdot n_2$ such that $n_1$ and $n_2$ are coprimes)
  • or a power of a prime itself (i.e. $n = x ^ y$ where $x$ is a prime)


I would think this is true since when you factorize $n$, if $n$ have two or more prime factors then those prime factors can be arranged to make $2$ coprimes. Otherwise if $n$ can only be factorized using one prime then it can't be the product of two coprimes.

Is this true? Is there any error in my reasoning?


Nothing is wrong with your reasoning. To make it clearer, there are two cases:

  1. There is only one prime that divides $n$.

  2. There are more than one prime that divides $n$. Let $p$ be a prime dividing $n$. And let $k$ be the largest natural number such that $p^k$ divides $n$. Then $n = p^k m$ for some $m \ne 1$ because some prime divides $n$ but not $p^k$. Also $\gcd(p^k,m) = 1$, so we are done.

| cite | improve this answer | |
  • $\begingroup$ By the way the condition that $n$ is composite is not necessary if by "power of a prime" you include $1$. $\endgroup$ – user21820 Aug 12 '16 at 15:10

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.