[proofplan] We prove the two implications separately. If $p$ is prime, then the Euclidean divisibility property follows from Euclid's lemma. Conversely, if $p$ has the Euclidean divisibility property, then any nontrivial factorization $p=dc$ would force $p$ to divide one of the proper positive factors, which is impossible. This rules out all nontrivial divisors, and the [prime gcd characterisation](/theorems/9878) then identifies $p$ as prime. [/proofplan] [step:Use the prime gcd characterisation and Bezout identity to prove the Euclidean divisibility property] Assume that $p$ is prime. Let $a,b \in \mathbb{Z}$ satisfy $p \mid ab$. Write $\gcd(a,p)$ for the positive greatest common divisor of the integers $a$ and $p$. Since $p \in \mathbb{N}$, $p \ge 2$, and $p$ is prime, the prime gcd characterisation [citetheorem:9878] gives \begin{align*} \gcd(a,p) \in \{1,p\}. \end{align*} If $\gcd(a,p)=p$, then the moreover part of [citetheorem:9878] gives $p \mid a$. If $\gcd(a,p)=1$, Bezout's identity for the integers gives integers $r,s \in \mathbb{Z}$ such that \begin{align*} ra+sp=1. \end{align*} Multiplying by $b$ gives \begin{align*} rab+spb=b. \end{align*} Since $p \mid ab$, there exists $m \in \mathbb{Z}$ such that $ab=pm$, and hence \begin{align*} b=p(rm+sb). \end{align*} Because $rm+sb \in \mathbb{Z}$, this proves $p \mid b$. Hence $p \mid a$ or $p \mid b$, so $p$ satisfies the Euclidean divisibility property. [guided] Assume that $p$ is prime. To prove the Euclidean divisibility property, we fix arbitrary integers $a,b \in \mathbb{Z}$ and assume $p \mid ab$. We must prove that $p \mid a$ or $p \mid b$. Write $\gcd(a,p)$ for the positive greatest common divisor of the integers $a$ and $p$. The useful split is according to this common divisor. The prime gcd characterisation [citetheorem:9878] applies because its hypotheses are exactly that $p \in \mathbb{N}$, $p \ge 2$, and $p$ is prime; these are in force. Therefore \begin{align*} \gcd(a,p) \in \{1,p\}. \end{align*} If $\gcd(a,p)=p$, the moreover part of [citetheorem:9878] says that $\gcd(a,p)=p$ if and only if $p \mid a$, so we are done in this case. It remains to handle the case $\gcd(a,p)=1$. Here we use Bezout's identity for the integers: because the greatest common divisor of $a$ and $p$ is $1$, there exist integers $r,s \in \mathbb{Z}$ such that \begin{align*} ra+sp=1. \end{align*} Multiplying this identity by $b$ gives \begin{align*} rab+spb=b. \end{align*} The assumption $p \mid ab$ means that there exists an integer $m \in \mathbb{Z}$ with $ab=pm$. Substituting this into the previous identity yields \begin{align*} b=rpm+spb=p(rm+sb). \end{align*} Since $rm+sb \in \mathbb{Z}$, the definition of divisibility gives $p \mid b$. Thus in both possible gcd cases we obtain $p \mid a$ or $p \mid b$. Since $a,b \in \mathbb{Z}$ were arbitrary, $p$ satisfies the Euclidean divisibility property. [/guided] [/step] [step:Rule out a nontrivial factor of a Euclidean prime] Assume conversely that for every $a,b \in \mathbb{Z}$, if $p \mid ab$, then $p \mid a$ or $p \mid b$. Let $d \in \mathbb{N}$ be a positive divisor of $p$, so there exists $c \in \mathbb{N}$ with \begin{align*} p = dc. \end{align*} Suppose, for contradiction, that $1 < d < p$. Since $p=dc$ and $d,c \in \mathbb{N}$, the integer $c$ is positive. Also $c \neq 1$, because $c=1$ would give $d=p$, contrary to $d<p$. Finally, $d>1$ and $p=dc$ give $c=p/d<p$. Thus $1<c<p$ as well. Since $p=dc$, we have $p \mid dc$. Applying the Euclidean divisibility property to the integers $d,c \in \mathbb{Z}$ gives $p \mid d$ or $p \mid c$. If $p \mid d$, then $d=pk$ for some $k \in \mathbb{Z}$, and positivity of $d$ gives $k \ge 1$, hence $d \ge p$, contradicting $d<p$. If $p \mid c$, the same argument gives $c \ge p$, contradicting $c<p$. Therefore no such divisor $d$ exists. [guided] Assume that $p$ has the Euclidean divisibility property: for every $a,b \in \mathbb{Z}$, if $p \mid ab$, then $p \mid a$ or $p \mid b$. We prove that $p$ has no positive divisor strictly between $1$ and $p$. Let $d \in \mathbb{N}$ be a positive divisor of $p$. By the definition of divisibility in $\mathbb{N}$, there exists $c \in \mathbb{N}$ such that \begin{align*} p=dc. \end{align*} Suppose for contradiction that $1<d<p$. Since $c \in \mathbb{N}$, $c$ is positive. If $c=1$, then $p=d$, contradicting $d<p$, so $c>1$. Also $d>1$ and $p=dc$ imply $c=p/d<p$. Hence \begin{align*} 1<c<p. \end{align*} Now $p=dc$ implies $p \mid dc$. The Euclidean divisibility property applies to $d,c \in \mathbb{Z}$, so $p \mid d$ or $p \mid c$. If $p \mid d$, then there exists $k \in \mathbb{Z}$ with $d=pk$. Since $d>0$ and $p>0$, we must have $k \ge 1$, and therefore $d=pk \ge p$, contradicting $d<p$. The case $p \mid c$ is identical with $c$ in place of $d$: there exists $k \in \mathbb{Z}$ with $c=pk$, positivity gives $k \ge 1$, and hence $c \ge p$, contradicting $c<p$. Both alternatives forced by the Euclidean divisibility property are impossible. Therefore no divisor $d \in \mathbb{N}$ with $1<d<p$ exists. [/guided] [/step] [step:Verify the prime gcd characterisation and conclude primality] We have shown that every positive divisor $d$ of $p$ satisfies $d=1$ or $d=p$. For each $a \in \mathbb{Z}$, the integer $\gcd(a,p)$ is positive and divides $p$, and hence \begin{align*} \gcd(a,p) \in \{1,p\}. \end{align*} The prime gcd characterisation [citetheorem:9878] applies because $p \in \mathbb{N}$ and $p \ge 2$ are hypotheses of the present theorem, and we have verified its gcd condition for every $a \in \mathbb{Z}$. Therefore $p$ is prime. This proves the reverse implication and completes the equivalence. [/step]