Show that any composite three-digit number must have a prime factor

[Math100]

Homework Statement

Show that any composite three-digit number must have a prime factor less than or equal to $31$.

Relevant Equations

None.

Proof:

Suppose for the sake of contradiction that any composite three-digit number
must have a prime factor not less than or equal to $31$.
Let $n$ be any composite three-digit number such that $n=ab$ for
some $a,b\in\mathbb{Z}$ where $a,b>1$.
Note that the smallest prime factor greater than $31$ is $37$.
Then we have $a,b\geq 37$.
Thus $n=ab\geq (37)^2=1369$.
This is a contradiction because $1369$ is not a composite three-digit number.
Therefore, any composite three-digit number must have a prime factor less than or equal to $31$.

 

[Mark44]

Then we have $a,b\geq 37$.

Better would be "$max(a, b) \ge 37$"
The largest three-digit number is 999. $\sqrt{999} \approx 31.61$, so if $n = ab$ is a three-digit composite number that is smaller than 999, the larger of its prime factors must be less than or equal to 31.

 

[Mark44]

I omitted the fact that for any composite, positive integer N, the largest prime factor must be less than or equal to $\sqrt N$. You might want to prove that as a lemma that supports the problem you're working on.

 

[Math100]

I omitted the fact that for any composite, positive integer N, the largest prime factor must be less than or equal to $\sqrt N$. You might want to prove that as a lemma that supports the problem you're working on.

Do I need to change my proof to another method? Or is proof by contradiction okay?

 

[Mark44]

I don't see anything wrong with your proof, except that it less direct than it could be.

 

[Math100]

I don't see anything wrong with your proof, except that it less direct than it could be.

About where should I insert the lemma which you've mentioned?

 

[Mark44]

About where should I insert the lemma which you've mentioned?

A lemma should come before a proof that refers to it.

 

[Math100]

Lemma: For any composite positive integer $N$,
the largest prime factor must be less than or equal to $\sqrt{N}$.

Proof:

Note that the largest composite three-digit number is $999$.
Thus $\sqrt{N}=\sqrt{999}\approx 31.61$.
Therefore, any composite three-digit number must have a prime factor
less than or equal to $31$.

 

[Mark44]

But you should provide a proof of the lemma...

 

[PeroK]

Homework Statement:: Show that any composite three-digit number must have a prime factor less than or equal to $31$.
Relevant Equations:: None.

Proof:

Suppose for the sake of contradiction that any composite three-digit number
must have a prime factor not less than or equal to $31$.

This is not the negation of the original proposition. The negation should be:

There exists a composite three-digit number with no primes factors less than or equal to 31.