7
$\begingroup$

Q: What is the largest possible prime factor of a composite three digit integer?

A: The largest $3$-digit is $999$ and $\sqrt {999}=31.61....$ and the largest prime factor less than this is $31$.

The above is one example showing in the discrete math textbook under theorem

If $n$ is composite, then $n$ has a prime divisor $p$ such that $p\le \sqrt n$.

I found this question is unfounded. Let's say $37$. Basically it is one of the prime factor of $740$. So the answer provided is wrong. Am I right? I think the answer should be $499$.

$\endgroup$
3
  • $\begingroup$ $714 / 37$ is not an integer. However what the theorem says is that there is a prime factor which is less than $\sqrt{n}$. It doesn't say that all prime factor must be less than $\sqrt{n}$. Take for example $82 = 2 \cdot 41$. Clearly one factor ($41$) is larger than $\sqrt{82} \approx 9.05$ but there is also the factor $2$ which satisfies the theorem. $\endgroup$
    – Zubzub
    Mar 9, 2017 at 9:22
  • $\begingroup$ @Zubzub I typed wrongly, I mean 740. I am wondering the textbook question was wrong. $\endgroup$ Mar 9, 2017 at 9:25
  • 1
    $\begingroup$ I believe you are correct in saying that the answer to the problem as stated should be $499$. $\endgroup$ Mar 9, 2017 at 9:25

2 Answers 2

4
$\begingroup$

Either the question as given to you is erroneous, or you copied it incorrectly. I will assume this is the former rather than the latter.

Remember that 2 is a prime number, too. So if $n = 2p$, with $p$ a prime number, then, for sufficiently large $n > 4$, we would see 2 is much smaller than $\sqrt n$, and $p$ is much greater.

The $n$ we're looking for is much greater than 99 but certainly less than 1000. We see that $999 = 3^3 \times 37$, but $998 = 2 \times 499$. We have $\sqrt{998} \approx 31.5911$, and the least prime factor, 2, is indeed less than 31. But 499 is certainly greater than 32.

So you're right: as you have the question, the correct answer is indeed 499.

Just to be absolutely sure: could the answer be 503? No, because $2 \times 503 = 1006$, which has four digits.

$\endgroup$
2
$\begingroup$

If the question is:

What is the largest possible minimum prime factor of a composite three digit integer?

(or something similar) then the answer as given by the book, $31$, is correct, because any composite number must have a factor less than or equal to its square root.

Otherwise, as already observed, a number of the form $2p$ with $p$ prime will give you the largest prime factor of a composite, in this case $499$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .