= Solution
Suppose $p$ is a <prime number>, $p\mid xy$ and $p\nmid x$. Since the only positive divisors of $p$ are one and $p$, the <greatest common divisor> of $p$ and $x$ is one. By <Bézout's identity>, integers $u,v$ exist with $up+vx=1$. Multiplying by $y$ gives $upy+vxy=y$. Both terms on the left are divisible by $p$, so $p\mid y$. Thus <Euclid lemma> gives
$$
\boxed{p\mid xy\ \Longrightarrow\ p\mid x\ \text{or}\ p\mid y.}
$$
The <Fundamental theorem of arithmetic> says that every positive integer greater than one is a product of <prime numbers>, uniquely up to their order. Existence follows by strong <mathematical induction>: if $n$ is prime it already has a factorization; otherwise $n=ab$ with $1<a,b<n$, and the factorizations of $a,b$ combine to factor $n$.
For uniqueness, suppose $p_1\cdots p_r=q_1\cdots q_s$ are two prime factorizations. Repeated application of <Euclid lemma> makes $p_1$ divide one of the $q_j$, so primality forces $p_1=q_j$. Reorder that factor to the front, cancel it and repeat. Neither side can retain extra primes when the other has become one, since every prime exceeds one. The two multisets are therefore identical. For a negative integer there is additionally the uniquely determined sign; one has the empty positive factorization, and zero is excluded. \b[The prime-product divisibility lemma is the step which makes factorization unique.]
Back to article page
