Elementary demonstration; $p$ prime, $1 \lt a \lt p$, $\;1 \lt b \lt p \quad$ Then $ p\nmid a b$ 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).
 A: 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.
A: If p divides ab, then it divides a or b (I'm not sure if you covered this; you can try to prove this as an exercise otherwise). This implies that it is less than or equal to a or b (since 1 is less than a and b), which contradicts the fact that a is less than p and b is less than p.
A: Well,that's not true
Just take one counterexample p=7 (prime greater than 2)
Take a=3
b=4
3.4=12 which is not divisible by 7
