Exercise 459Number theory › Divisibility and gcdHigh schoolAdded 3 Nov 2026

Every integer has a prime divisor

#primes#divisor#well-ordering

Statement

Show that every integer $n\ge2$ has at least one prime divisor.

Hint

Use well-ordering on the set of divisors of $n$ greater than $1$ .

Show solutionHide solution

Solution

Well-ordering. Let $D=\{d\ge2:d\mid n\}$ , nonempty since $n\in D$ . Let $p=\min D$ .

$p$ is prime. If $p=ab$ with $1<a,b<p$ , then $a\mid p\mid n$ , so $a\in D$ , contradicting minimality of $p$ . Hence $p$ has no nontrivial factorization.

Conclusion. $p$ is a prime divisor of $n$ .

Every integer has a prime divisor

Statement

Solution

More problems in Divisibility and gcd