[proofplan] We use only the defining properties of the greatest common divisor: $\gcd(a,p)$ is the greatest positive integer dividing both $a$ and $p$. If $p$ is prime, every positive divisor of $p$ is either $1$ or $p$, so the gcd has one of those two values. Conversely, if every gcd with $p$ is either $1$ or $p$, then a proper divisor of $p$ would give a forbidden gcd value. The final equivalence follows by comparing the statement $\gcd(a,p)=p$ with the divisibility condition $p \mid a$. [/proofplan]

[step:Show that primality forces every gcd with $p$ to be either $1$ or $p$] Assume that $p$ is prime. Let $a \in \mathbb{Z}$ be arbitrary, and define \begin{align*} g := \gcd(a,p). \end{align*} By the definition of greatest common divisor, $g$ is a positive integer, $g \mid a$, and $g \mid p$. Since $p$ is prime, the only positive divisors of $p$ are $1$ and $p$. Therefore $g \in \{1,p\}$. Since $a \in \mathbb{Z}$ was arbitrary, for every $a \in \mathbb{Z}$ one has $\gcd(a,p) \in \{1,p\}$. [/step]

[step:Use a proper divisor to prove the converse]Assume that for every $a \in \mathbb{Z}$, \begin{align*} \gcd(a,p) \in \{1,p\}. \end{align*} We prove that $p$ is prime. Suppose, for contradiction, that $p$ is not prime. Since $p \ge 2$, the negation of primality gives a positive divisor $d \in \mathbb{N}$ of $p$ such that \begin{align*} 1 < d < p. \end{align*} Because $d \mid p$ and $d \mid d$, the integer $d$ is a positive common divisor of $d$ and $p$. Conversely, every positive common divisor of $d$ and $p$ divides $d$, hence is at most $d$. Thus the greatest positive common divisor of $d$ and $p$ is $d$: \begin{align*} \gcd(d,p)=d. \end{align*} Applying the assumed gcd condition with $a=d$ gives \begin{align*} d=\gcd(d,p) \in \{1,p\}, \end{align*} which contradicts $1<d<p$. Hence $p$ is prime.[/step]

[guided]Assume that for every $a \in \mathbb{Z}$, the value $\gcd(a,p)$ is either $1$ or $p$. We want to show that $p$ has no positive divisors except $1$ and $p$. Suppose instead that $p$ is not prime. Since $p \in \mathbb{N}$ and $p \ge 2$, non-primality means that there exists a positive divisor $d \in \mathbb{N}$ of $p$ with \begin{align*} 1 < d < p. \end{align*} The idea is to test the assumed gcd condition on the special integer $a=d$. This choice is useful because $d$ is already known to divide $p$, and every integer divides itself. We now compute $\gcd(d,p)$ from the definition. Since $d \mid d$ and $d \mid p$, the integer $d$ is a positive common divisor of $d$ and $p$. If $c \in \mathbb{N}$ is any positive common divisor of $d$ and $p$, then in particular $c \mid d$, so $c \le d$. Therefore no positive common divisor of $d$ and $p$ is larger than $d$, while $d$ itself is a positive common divisor. Hence \begin{align*} \gcd(d,p)=d. \end{align*} Now apply the assumed property with $a=d$. It gives \begin{align*} \gcd(d,p) \in \{1,p\}. \end{align*} Substituting $\gcd(d,p)=d$, we obtain \begin{align*} d \in \{1,p\}. \end{align*} This contradicts the strict inequalities $1<d<p$. Therefore the supposition that $p$ is not prime is impossible, and $p$ is prime.[/guided]

[step:Identify the gcd value $p$ exactly with divisibility by $p$] Let $a \in \mathbb{Z}$ be arbitrary, and define \begin{align*} g := \gcd(a,p). \end{align*} First assume that $g=p$. Since the greatest common divisor divides each argument, $g \mid a$. Substituting $g=p$ gives $p \mid a$. Conversely, assume that $p \mid a$. Since $p \mid p$ as well, the integer $p$ is a positive common divisor of $a$ and $p$. By the defining maximality of $g=\gcd(a,p)$, this gives $p \le g$. Also $g \mid p$, so $g \le p$ because both $g$ and $p$ are positive. Therefore $g=p$, that is, \begin{align*} \gcd(a,p)=p. \end{align*} Since $a \in \mathbb{Z}$ was arbitrary, for every $a \in \mathbb{Z}$ one has $\gcd(a,p)=p$ if and only if $p \mid a$. [/step]