Let n Z and n 1 Prove that if n is not divisible by any pri

Let n Z and n > 1. Prove that if n is not divisible by any prime number less than or equal to n, then n is a prime number.

Please show this using contradiction and the fundamental theorem of arithmetic if you can. Thanks!

Solution

If n is composite, then n = ab where a > 1 and b > 1.

For convenience, suppose a b.

Let p be a prime divisor of a.

Thus p a b.

So p² a² ab = n

Since p | a and a | n we have p | n.

So, p n