Given that the number 8881 is not a prime number, prove by contradiction that it has a prime factor that is at most 89

Question

Can anyone help with this question?

Given that the number $8881$ is not a prime number, prove by contradiction that it has a prime factor that is at most $89$.

From the comments:

This was my approach: assume all prime factors > 89. The next prime number after 89 is 97. The smallest number composed of only 97 is 97^2 > 8881. However I realize that the reasoning on this is flawed i.e. showing that all prime factors can't be greater than 89 isn't the same as showing that at least one prime factor isn't greater than 89.

Answer 1

Why do you think your reasonning is flawed ?

If all prime factors where superior to $89$, they would be at least $97$. Counting them with their multiplicity, if there was only one such factor it would be $8881$, which contradicts the given fact that $8881$ is not prime. If there are at least two (possibly equal) factors $a$ and $b$, then $ab\leq 8881$ but $ab\geq 97*97>8881$, contradiction.

Your reasonning could be better worded but it is correct.

Answer 2

Hint:

If a number $n$ is composite, it has a prime factor $<\lfloor\sqrt n\rfloor$. Now $\lfloor\sqrt 8881\rfloor=94$.

Answer 3

You're on the right lines. If $8881$ is not prime, it must have at least one prime factor not equal to itself.

If it has no prime factors less than or equal to $89$, then it must have only prime factors greater than or equal to $97$, which is the next prime up from $89$. You've already found the smallest natural number which has prime factors greater than or equal to $97$, so can you draw a conclusion from this?

Answer 4

ADDED: THERE REALLY IS A PRIME FACTOR OF $8881$ THAT IS NO LARGER THAN $89.$ IT IS

$$ \huge 83 $$ It is possible, without knowing anything other than the size of $8881,$ to think that there might some prime factors larger than $89,$ or perhaps not. In this case, yes, $107$ is larger than $89.$ It is not difficult to produce numbers for which all prime factors are smaller than the square root of the number, such as $105 = 3 \cdot 5 \cdot 7, $ with $sqrt {105} \approx 10.24$

There is a simple pattern that begins with $5^2 = 25,$ $15^2 = 225,$ $25^2 = 625,$ $35^2 = 1225,$ $45^2 = 2025.$ You just take the initial digit and multiply it by one more, as in $4 \cdot 5 = 20.$ The you follow by the $25.$ In particular, $95^2 = 9025.$ To get from $8881$ to $9000$ you need to add $119,$ then another $25$ to get to $9025,$ or $119+25 = 144.$ So $$ 8881 + 144 = 9025, $$ $$ 8881 = 9025 - 144, $$ $$ 8881 = 95^2 - 12^2, $$ $$ 8881 = (95 - 12)(95+12), $$ $$ 8881 = 83 \cdot 107. $$ And both are prime, with $83 < 89.$

That is, this is one you can do in your head.