Prove: If $(a, p) = 1$ , $0 < a < p$ , then $p$ is prime

Question

I know that obviously if the GCD of two numbers is 1 and $p$ is the larger number, then it has to be prime. I'm just unsure where to even begin trying to explain this in a proof.

Answer 1

Suppose the GCD is not 1. Then, something other than 1 divides both $a$ and $p$. Since $a < p$, this means $p$ is composite.

Answer 2

I recommend contradiction: Suppose that $p$ has a nontrivial factorization $p = rs$, where $1 < r, s < p.$ What can you say about the gcd of $p$ and $r$?

But even more than that, I recommend writing down the problem statement really clearly:

Suppose that for all $a$ with $0 < a < p$, we have $(a, p) = 1.$ Then show $p$ must be prime.