Exercise 550Number theory › PrimesHigh schoolAdded 3 Nov 2026

Characterization of primes

#primes#characterization#divisors

Statement

Show that $n>1$ is prime iff $n\mid ab\Rightarrow n\mid a$ or $n\mid b$ for all integers $a,b$ .

Hint

Forward: Euclid's lemma. Converse: if $n=ab$ with $1<a,b<n$ , then $n\mid ab$ but $n\nmid a,b$ .

Show solutionHide solution

Forward. Suppose $n$ prime and $n\mid ab$ . Euclid's lemma gives $n\mid a$ or $n\mid b$ .

Converse. If $n$ is composite, write $n=pq$ with $1<p,q<n$ . Then $n\mid pq$ but $n\nmid p$ and $n\nmid q$ (since $p,q<n$ ). Contradiction.

Conclusion. The characterization holds.