[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.
[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]
[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]
