- #1

Math100

- 766

- 207

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

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