Update: If this question is of interest, you can also click here.
Update: Using Bill Dubuque's lemma and logic proving Euclid's lemma, we can supply an elementary proof.
To get a contradiction, assume than $p \mid a b$.
Let $S = \{n \in \Bbb N \, | \, p \mid nb \}$. Then $p \in S$ and $a \in S$. Moreover, $S$ is closed under subtraction.
Let $d = \text{min(}S\text{)}$. By the lemma, $d \mid p$, so $d = 1$ or $d = p$.
If $d = 1$, since $d \in S$, it must follow that $p \mid (1 \times b)$, which is absurd since $b \lt p$.
By the lemma, $d \mid a$, so if $d = p$ then $p \mid a$, which is absurd since $a \lt p$.
I've been motivated (see this) to prove the following result using only elementary techniques.
Let $p$ be a prime greater than $2$.
Let $1 \lt a \lt p$
Let $1 \lt b \lt p$
Then
$$\tag 1 p\nmid a b$$
I think that this is as simple as first showing that
$$ \text{For every integer n } \ge 1 \text{ such that } p\nmid n, \; \; p\nmid na$$
and ironing out some details.
Using only the 'first page' of elementary theory of the natural numbers/integers (for example Euclidean division, the construction of $\Bbb Z$, the existence of prime factorizations and that modular arithmetic is well-defined), can this approach work for proving $\text{(1)}$?
Besides answering yes in the comments, a proof would be appreciated (this elementary approach can be exhausting).
You need some more than the definition of prime to prove this. The reason is that in other rings (systems of 'numbers' [they can actually be numbers, polynomials or any 'thing' that you can sum and multiply] with sum and product) there are elements that can be only divided (essentially) by $1$ and themselves, but there are pairs of this 'numbers' $a,b$ such that $p\mid ab$ but $p$ does not divide $a$ or $b$. A well-known example is $2\cdot3=(\sqrt {-5}+1)(-\sqrt {-5}+1)$.
The best-trodden path for natural numbers is through Euclid's algorithm and Bezout's identity. It is not difficult to read, but kind of long to post here and easy to find.