Proof

It follows from the definition of prime numbers that $p > 1$ and that $p$ has only the trivial divisors $1$ and $p$.
Therefore the greatest common divisor of $p$ is $p$ itself.
Now, if $p$ divides the integer $a$, then the greatest common divisor of $p$ and $a$ must be $p$.
The first part of the proposition follows: $p\mid a\Rightarrow \gcd(p,a)=p.$
Now, assume that $p\not\mid a$.
- Because $1$ and $p$ are the only divisors of $p$, we must have either $\gcd(p,a)=1$, or $\gcd(p,a)=p$.
- Because $p\not\mid a$, only the first is possible.
This completes the proof

\[p\not |a\Longrightarrow \gcd(p,a)=1.\]

∎

Thank you to the contributors under CC BY-SA 4.0!

Landau, Edmund: "Vorlesungen über Zahlentheorie, Aus der Elementaren Zahlentheorie", S. Hirzel, Leipzig, 1927