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

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

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.

• what has been tried ? and where are you stuck ? – user451844 Aug 11 '17 at 15:28
• What have you tried? How do you think a solution should go? Where do think the 89 comes from? – sharding4 Aug 11 '17 at 15:28
• I suggest you edit your question to include what you've tried, before it gets closed as off topic. – Shaun Aug 11 '17 at 15:33
• If $C$ is not a prime number, then it contains at least one factor that is less than or equal to $\sqrt{C}$ – steven gregory Aug 19 '17 at 5:21

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.

• @Evargelo Thanks for your response. It seems to me that showing that all prime factors of 8881 can't be > 89 isn't the same as showing that at least one prime factor of 8881 can't be greater that 89. That's why I believe it to be a flawed approach. – user7875067 Aug 11 '17 at 15:56
• You have to show that $8881$ has a prime factor that is at most 89. It means exactly the same than "at least one prime factor of 8881 isn't greater that 89", doesn't it ? – Evargalo Aug 11 '17 at 16:05
• @Evargelo The above proof shows that all of 8881's prime factors can't be > 89. But what about the case that some of 8881's prime factors are greater than 89, and some are less? – user7875067 Aug 11 '17 at 16:18
• In that case, at least one of them is smaller than 89. That's exactly what you want to prove. – Evargalo Aug 12 '17 at 11:09
• You're right. I had an initial misunderstanding on what the question was asking (i.e. show that all prime factors of 8881 are < 89). Thanks for your input. – user7875067 Aug 12 '17 at 12:10

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?

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.

• Elegant mental arithmetic and good tricks to know (squares of multiples of $5$ and factoring by difference of squares) but not a direct answer to the OPs question and therefore not generalizable to similar questions. +1 anyway of course. – Ethan Bolker Aug 11 '17 at 18:37
• @EthanBolker right. The other answers are trying to address the original question in good faith, pretty well I think. This is, by the way, associated with Fermat; I did do the other squares up to 10000 in my head, you get accustomed to it, in this case $(100 - n)^2 = 10000 - 200n + n^2.$ en.wikipedia.org/wiki/Fermat's_factorization_method – Will Jagy Aug 11 '17 at 18:43
• For that matter, $(95 - t)^2 = 9025- 190t + t^2.$ But $t=1$ already gives $8836,$ too low. – Will Jagy Aug 11 '17 at 18:52
• This question was in a book I am studying. It suggests obtaining a solution without factorizing 8881. It would seem that the question is flawed since, as Will has so elegantly shown, 8881 does have a prime factor > 89. The book is in its 3rd edition too! – user7875067 Aug 11 '17 at 20:05
• @WillJagy I see. Thanks for the clarification. – user7875067 Aug 11 '17 at 22:24

Hint:

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

• I am not sure if the OP is allowed to use this theorem, though. – Evargalo Aug 11 '17 at 15:45
• Do you think so? It's a high school result. – Bernard Aug 11 '17 at 15:47
• We obviously miss context, but the exercise looks like the assignment I'd give high schoolers for the day when we will introduce the theorem... – Evargalo Aug 11 '17 at 15:48
• (just for the record, I'm not the downvoter) – Evargalo Aug 11 '17 at 16:07