0
$\begingroup$

Let $n$ be a composite number so that it has at most one prime factor such that $p \leq \sqrt{n}$. Find all ways how you can factor $n$ and give examples.

My work:

We know that if $n$ is composite, there has to be at least one prime factor with such property. We also can deduce that for any other prime factors of $n$ - lets call them $q_i$ there can be at most one of them because $q_i^2 > n$. So the different ways you could factor $n$ I came up with are

1) $n=p^k$ - for example $16=2^4$. 2) $n=p^k \cdot q$ - for example $44 = 2^2 \cdot 11$. 3) $n=p\cdot q$ - for example $22 = 2 \cdot 11$.

Are there any ways that I am missing?

$\endgroup$
  • 2
    $\begingroup$ Looks good to me. Note that your case 3 ($n=p\cdot q$) is just case 2 with $k=1$. $\endgroup$ – TonyK Mar 3 at 14:46
1
$\begingroup$

You already found out that at most one prime factor can exceed $\sqrt{n}$ (this is true for every positive integer $n$). Moreover, we know that we must have exactly one prime factor $p\le \sqrt{n}$ (Because of the mentioned condition).

If no prime factor exceeeds $\sqrt{n}$, then we must have a prime power.

If one prime factor exceeds $\sqrt{n}$, the exponent corresponding to this prime must be $1$, so we must have a prime power multiplied with this prime.

Hence , you did not overlook examples.

$\endgroup$

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.